aboutsummaryrefslogtreecommitdiff
path: root/crates/ra_hir/src/nameres.rs
diff options
context:
space:
mode:
Diffstat (limited to 'crates/ra_hir/src/nameres.rs')
-rw-r--r--crates/ra_hir/src/nameres.rs558
1 files changed, 0 insertions, 558 deletions
diff --git a/crates/ra_hir/src/nameres.rs b/crates/ra_hir/src/nameres.rs
deleted file mode 100644
index 32a6ab474..000000000
--- a/crates/ra_hir/src/nameres.rs
+++ /dev/null
@@ -1,558 +0,0 @@
1//! This module implements import-resolution/macro expansion algorithm.
2//!
3//! The result of this module is `CrateDefMap`: a data structure which contains:
4//!
5//! * a tree of modules for the crate
6//! * for each module, a set of items visible in the module (directly declared
7//! or imported)
8//!
9//! Note that `CrateDefMap` contains fully macro expanded code.
10//!
11//! Computing `CrateDefMap` can be partitioned into several logically
12//! independent "phases". The phases are mutually recursive though, there's no
13//! strict ordering.
14//!
15//! ## Collecting RawItems
16//!
17//! This happens in the `raw` module, which parses a single source file into a
18//! set of top-level items. Nested imports are desugared to flat imports in
19//! this phase. Macro calls are represented as a triple of (Path, Option<Name>,
20//! TokenTree).
21//!
22//! ## Collecting Modules
23//!
24//! This happens in the `collector` module. In this phase, we recursively walk
25//! tree of modules, collect raw items from submodules, populate module scopes
26//! with defined items (so, we assign item ids in this phase) and record the set
27//! of unresolved imports and macros.
28//!
29//! While we walk tree of modules, we also record macro_rules definitions and
30//! expand calls to macro_rules defined macros.
31//!
32//! ## Resolving Imports
33//!
34//! We maintain a list of currently unresolved imports. On every iteration, we
35//! try to resolve some imports from this list. If the import is resolved, we
36//! record it, by adding an item to current module scope and, if necessary, by
37//! recursively populating glob imports.
38//!
39//! ## Resolving Macros
40//!
41//! macro_rules from the same crate use a global mutable namespace. We expand
42//! them immediately, when we collect modules.
43//!
44//! Macros from other crates (including proc-macros) can be used with
45//! `foo::bar!` syntax. We handle them similarly to imports. There's a list of
46//! unexpanded macros. On every iteration, we try to resolve each macro call
47//! path and, upon success, we run macro expansion and "collect module" phase
48//! on the result
49
50mod per_ns;
51mod collector;
52#[cfg(test)]
53mod tests;
54
55use std::sync::Arc;
56
57use hir_def::{builtin_type::BuiltinType, CrateModuleId};
58use hir_expand::diagnostics::DiagnosticSink;
59use once_cell::sync::Lazy;
60use ra_arena::Arena;
61use ra_db::{Edition, FileId};
62use ra_prof::profile;
63use ra_syntax::ast;
64use rustc_hash::{FxHashMap, FxHashSet};
65use test_utils::tested_by;
66
67use crate::{
68 db::{AstDatabase, DefDatabase},
69 ids::MacroDefId,
70 nameres::diagnostics::DefDiagnostic,
71 Adt, AstId, Crate, HirFileId, MacroDef, Module, ModuleDef, Name, Path, PathKind, Trait,
72};
73
74pub use self::per_ns::{Namespace, PerNs};
75
76pub use hir_def::nameres::raw::ImportId;
77
78/// Contains all top-level defs from a macro-expanded crate
79#[derive(Debug, PartialEq, Eq)]
80pub struct CrateDefMap {
81 krate: Crate,
82 edition: Edition,
83 /// The prelude module for this crate. This either comes from an import
84 /// marked with the `prelude_import` attribute, or (in the normal case) from
85 /// a dependency (`std` or `core`).
86 prelude: Option<Module>,
87 extern_prelude: FxHashMap<Name, ModuleDef>,
88 root: CrateModuleId,
89 modules: Arena<CrateModuleId, ModuleData>,
90
91 /// Some macros are not well-behavior, which leads to infinite loop
92 /// e.g. macro_rules! foo { ($ty:ty) => { foo!($ty); } }
93 /// We mark it down and skip it in collector
94 ///
95 /// FIXME:
96 /// Right now it only handle a poison macro in a single crate,
97 /// such that if other crate try to call that macro,
98 /// the whole process will do again until it became poisoned in that crate.
99 /// We should handle this macro set globally
100 /// However, do we want to put it as a global variable?
101 poison_macros: FxHashSet<MacroDefId>,
102
103 diagnostics: Vec<DefDiagnostic>,
104}
105
106impl std::ops::Index<CrateModuleId> for CrateDefMap {
107 type Output = ModuleData;
108 fn index(&self, id: CrateModuleId) -> &ModuleData {
109 &self.modules[id]
110 }
111}
112
113#[derive(Default, Debug, PartialEq, Eq)]
114pub struct ModuleData {
115 pub(crate) parent: Option<CrateModuleId>,
116 pub(crate) children: FxHashMap<Name, CrateModuleId>,
117 pub(crate) scope: ModuleScope,
118 /// None for root
119 pub(crate) declaration: Option<AstId<ast::Module>>,
120 /// None for inline modules.
121 ///
122 /// Note that non-inline modules, by definition, live inside non-macro file.
123 pub(crate) definition: Option<FileId>,
124}
125
126#[derive(Debug, Default, PartialEq, Eq, Clone)]
127pub struct ModuleScope {
128 items: FxHashMap<Name, Resolution>,
129 /// Macros visable in current module in legacy textual scope
130 ///
131 /// For macros invoked by an unquatified identifier like `bar!()`, `legacy_macros` will be searched in first.
132 /// If it yields no result, then it turns to module scoped `macros`.
133 /// It macros with name quatified with a path like `crate::foo::bar!()`, `legacy_macros` will be skipped,
134 /// and only normal scoped `macros` will be searched in.
135 ///
136 /// Note that this automatically inherit macros defined textually before the definition of module itself.
137 ///
138 /// Module scoped macros will be inserted into `items` instead of here.
139 // FIXME: Macro shadowing in one module is not properly handled. Non-item place macros will
140 // be all resolved to the last one defined if shadowing happens.
141 legacy_macros: FxHashMap<Name, MacroDef>,
142}
143
144static BUILTIN_SCOPE: Lazy<FxHashMap<Name, Resolution>> = Lazy::new(|| {
145 BuiltinType::ALL
146 .iter()
147 .map(|(name, ty)| {
148 (name.clone(), Resolution { def: PerNs::types(ty.clone().into()), import: None })
149 })
150 .collect()
151});
152
153/// Legacy macros can only be accessed through special methods like `get_legacy_macros`.
154/// Other methods will only resolve values, types and module scoped macros only.
155impl ModuleScope {
156 pub fn entries<'a>(&'a self) -> impl Iterator<Item = (&'a Name, &'a Resolution)> + 'a {
157 //FIXME: shadowing
158 self.items.iter().chain(BUILTIN_SCOPE.iter())
159 }
160
161 /// Iterate over all module scoped macros
162 pub fn macros<'a>(&'a self) -> impl Iterator<Item = (&'a Name, MacroDef)> + 'a {
163 self.items
164 .iter()
165 .filter_map(|(name, res)| res.def.get_macros().map(|macro_| (name, macro_)))
166 }
167
168 /// Iterate over all legacy textual scoped macros visable at the end of the module
169 pub fn legacy_macros<'a>(&'a self) -> impl Iterator<Item = (&'a Name, MacroDef)> + 'a {
170 self.legacy_macros.iter().map(|(name, def)| (name, *def))
171 }
172
173 /// Get a name from current module scope, legacy macros are not included
174 pub fn get(&self, name: &Name) -> Option<&Resolution> {
175 self.items.get(name).or_else(|| BUILTIN_SCOPE.get(name))
176 }
177
178 pub fn traits<'a>(&'a self) -> impl Iterator<Item = Trait> + 'a {
179 self.items.values().filter_map(|r| match r.def.take_types() {
180 Some(ModuleDef::Trait(t)) => Some(t),
181 _ => None,
182 })
183 }
184
185 fn get_legacy_macro(&self, name: &Name) -> Option<MacroDef> {
186 self.legacy_macros.get(name).copied()
187 }
188}
189
190#[derive(Debug, Clone, PartialEq, Eq, Default)]
191pub struct Resolution {
192 /// None for unresolved
193 pub def: PerNs,
194 /// ident by which this is imported into local scope.
195 pub import: Option<ImportId>,
196}
197
198impl Resolution {
199 pub(crate) fn from_macro(macro_: MacroDef) -> Self {
200 Resolution { def: PerNs::macros(macro_), import: None }
201 }
202}
203
204#[derive(Debug, Clone)]
205struct ResolvePathResult {
206 resolved_def: PerNs,
207 segment_index: Option<usize>,
208 reached_fixedpoint: ReachedFixedPoint,
209}
210
211impl ResolvePathResult {
212 fn empty(reached_fixedpoint: ReachedFixedPoint) -> ResolvePathResult {
213 ResolvePathResult::with(PerNs::none(), reached_fixedpoint, None)
214 }
215
216 fn with(
217 resolved_def: PerNs,
218 reached_fixedpoint: ReachedFixedPoint,
219 segment_index: Option<usize>,
220 ) -> ResolvePathResult {
221 ResolvePathResult { resolved_def, reached_fixedpoint, segment_index }
222 }
223}
224
225#[derive(Debug, Clone, Copy, PartialEq, Eq)]
226enum ResolveMode {
227 Import,
228 Other,
229}
230
231#[derive(Debug, Clone, Copy, PartialEq, Eq)]
232enum ReachedFixedPoint {
233 Yes,
234 No,
235}
236
237impl CrateDefMap {
238 pub(crate) fn crate_def_map_query(
239 // Note that this doesn't have `+ AstDatabase`!
240 // This gurantess that `CrateDefMap` is stable across reparses.
241 db: &impl DefDatabase,
242 krate: Crate,
243 ) -> Arc<CrateDefMap> {
244 let _p = profile("crate_def_map_query");
245 let def_map = {
246 let edition = krate.edition(db);
247 let mut modules: Arena<CrateModuleId, ModuleData> = Arena::default();
248 let root = modules.alloc(ModuleData::default());
249 CrateDefMap {
250 krate,
251 edition,
252 extern_prelude: FxHashMap::default(),
253 prelude: None,
254 root,
255 modules,
256 poison_macros: FxHashSet::default(),
257 diagnostics: Vec::new(),
258 }
259 };
260 let def_map = collector::collect_defs(db, def_map);
261 Arc::new(def_map)
262 }
263
264 pub(crate) fn krate(&self) -> Crate {
265 self.krate
266 }
267
268 pub(crate) fn root(&self) -> CrateModuleId {
269 self.root
270 }
271
272 pub(crate) fn prelude(&self) -> Option<Module> {
273 self.prelude
274 }
275
276 pub(crate) fn extern_prelude(&self) -> &FxHashMap<Name, ModuleDef> {
277 &self.extern_prelude
278 }
279
280 pub(crate) fn add_diagnostics(
281 &self,
282 db: &(impl DefDatabase + AstDatabase),
283 module: CrateModuleId,
284 sink: &mut DiagnosticSink,
285 ) {
286 self.diagnostics.iter().for_each(|it| it.add_to(db, module, sink))
287 }
288
289 pub(crate) fn find_module_by_source(
290 &self,
291 file_id: HirFileId,
292 decl_id: Option<AstId<ast::Module>>,
293 ) -> Option<CrateModuleId> {
294 let (module_id, _module_data) = self.modules.iter().find(|(_module_id, module_data)| {
295 if decl_id.is_some() {
296 module_data.declaration == decl_id
297 } else {
298 module_data.definition.map(|it| it.into()) == Some(file_id)
299 }
300 })?;
301 Some(module_id)
302 }
303
304 pub(crate) fn resolve_path(
305 &self,
306 db: &impl DefDatabase,
307 original_module: CrateModuleId,
308 path: &Path,
309 ) -> (PerNs, Option<usize>) {
310 let res = self.resolve_path_fp_with_macro(db, ResolveMode::Other, original_module, path);
311 (res.resolved_def, res.segment_index)
312 }
313
314 // Returns Yes if we are sure that additions to `ItemMap` wouldn't change
315 // the result.
316 fn resolve_path_fp_with_macro(
317 &self,
318 db: &impl DefDatabase,
319 mode: ResolveMode,
320 original_module: CrateModuleId,
321 path: &Path,
322 ) -> ResolvePathResult {
323 let mut segments = path.segments.iter().enumerate();
324 let mut curr_per_ns: PerNs = match path.kind {
325 PathKind::DollarCrate(crate_id) => {
326 let krate = Crate { crate_id };
327 if krate == self.krate {
328 tested_by!(macro_dollar_crate_self);
329 PerNs::types(Module::new(self.krate, self.root).into())
330 } else {
331 match krate.root_module(db) {
332 Some(module) => {
333 tested_by!(macro_dollar_crate_other);
334 PerNs::types(module.into())
335 }
336 None => return ResolvePathResult::empty(ReachedFixedPoint::Yes),
337 }
338 }
339 }
340 PathKind::Crate => PerNs::types(Module::new(self.krate, self.root).into()),
341 PathKind::Self_ => PerNs::types(Module::new(self.krate, original_module).into()),
342 // plain import or absolute path in 2015: crate-relative with
343 // fallback to extern prelude (with the simplification in
344 // rust-lang/rust#57745)
345 // FIXME there must be a nicer way to write this condition
346 PathKind::Plain | PathKind::Abs
347 if self.edition == Edition::Edition2015
348 && (path.kind == PathKind::Abs || mode == ResolveMode::Import) =>
349 {
350 let segment = match segments.next() {
351 Some((_, segment)) => segment,
352 None => return ResolvePathResult::empty(ReachedFixedPoint::Yes),
353 };
354 log::debug!("resolving {:?} in crate root (+ extern prelude)", segment);
355 self.resolve_name_in_crate_root_or_extern_prelude(&segment.name)
356 }
357 PathKind::Plain => {
358 let segment = match segments.next() {
359 Some((_, segment)) => segment,
360 None => return ResolvePathResult::empty(ReachedFixedPoint::Yes),
361 };
362 log::debug!("resolving {:?} in module", segment);
363 self.resolve_name_in_module(db, original_module, &segment.name)
364 }
365 PathKind::Super => {
366 if let Some(p) = self.modules[original_module].parent {
367 PerNs::types(Module::new(self.krate, p).into())
368 } else {
369 log::debug!("super path in root module");
370 return ResolvePathResult::empty(ReachedFixedPoint::Yes);
371 }
372 }
373 PathKind::Abs => {
374 // 2018-style absolute path -- only extern prelude
375 let segment = match segments.next() {
376 Some((_, segment)) => segment,
377 None => return ResolvePathResult::empty(ReachedFixedPoint::Yes),
378 };
379 if let Some(def) = self.extern_prelude.get(&segment.name) {
380 log::debug!("absolute path {:?} resolved to crate {:?}", path, def);
381 PerNs::types(*def)
382 } else {
383 return ResolvePathResult::empty(ReachedFixedPoint::No); // extern crate declarations can add to the extern prelude
384 }
385 }
386 PathKind::Type(_) => {
387 // This is handled in `infer::infer_path_expr`
388 // The result returned here does not matter
389 return ResolvePathResult::empty(ReachedFixedPoint::Yes);
390 }
391 };
392
393 for (i, segment) in segments {
394 let curr = match curr_per_ns.take_types() {
395 Some(r) => r,
396 None => {
397 // we still have path segments left, but the path so far
398 // didn't resolve in the types namespace => no resolution
399 // (don't break here because `curr_per_ns` might contain
400 // something in the value namespace, and it would be wrong
401 // to return that)
402 return ResolvePathResult::empty(ReachedFixedPoint::No);
403 }
404 };
405 // resolve segment in curr
406
407 curr_per_ns = match curr {
408 ModuleDef::Module(module) => {
409 if module.krate() != self.krate {
410 let path =
411 Path { segments: path.segments[i..].to_vec(), kind: PathKind::Self_ };
412 log::debug!("resolving {:?} in other crate", path);
413 let defp_map = db.crate_def_map(module.krate());
414 let (def, s) = defp_map.resolve_path(db, module.id.module_id, &path);
415 return ResolvePathResult::with(
416 def,
417 ReachedFixedPoint::Yes,
418 s.map(|s| s + i),
419 );
420 }
421
422 // Since it is a qualified path here, it should not contains legacy macros
423 match self[module.id.module_id].scope.get(&segment.name) {
424 Some(res) => res.def,
425 _ => {
426 log::debug!("path segment {:?} not found", segment.name);
427 return ResolvePathResult::empty(ReachedFixedPoint::No);
428 }
429 }
430 }
431 ModuleDef::Adt(Adt::Enum(e)) => {
432 // enum variant
433 tested_by!(can_import_enum_variant);
434 match e.variant(db, &segment.name) {
435 Some(variant) => PerNs::both(variant.into(), variant.into()),
436 None => {
437 return ResolvePathResult::with(
438 PerNs::types(e.into()),
439 ReachedFixedPoint::Yes,
440 Some(i),
441 );
442 }
443 }
444 }
445 s => {
446 // could be an inherent method call in UFCS form
447 // (`Struct::method`), or some other kind of associated item
448 log::debug!(
449 "path segment {:?} resolved to non-module {:?}, but is not last",
450 segment.name,
451 curr,
452 );
453
454 return ResolvePathResult::with(
455 PerNs::types(s),
456 ReachedFixedPoint::Yes,
457 Some(i),
458 );
459 }
460 };
461 }
462 ResolvePathResult::with(curr_per_ns, ReachedFixedPoint::Yes, None)
463 }
464
465 fn resolve_name_in_crate_root_or_extern_prelude(&self, name: &Name) -> PerNs {
466 let from_crate_root =
467 self[self.root].scope.get(name).map_or_else(PerNs::none, |res| res.def);
468 let from_extern_prelude = self.resolve_name_in_extern_prelude(name);
469
470 from_crate_root.or(from_extern_prelude)
471 }
472
473 pub(crate) fn resolve_name_in_module(
474 &self,
475 db: &impl DefDatabase,
476 module: CrateModuleId,
477 name: &Name,
478 ) -> PerNs {
479 // Resolve in:
480 // - legacy scope of macro
481 // - current module / scope
482 // - extern prelude
483 // - std prelude
484 let from_legacy_macro =
485 self[module].scope.get_legacy_macro(name).map_or_else(PerNs::none, PerNs::macros);
486 let from_scope = self[module].scope.get(name).map_or_else(PerNs::none, |res| res.def);
487 let from_extern_prelude =
488 self.extern_prelude.get(name).map_or(PerNs::none(), |&it| PerNs::types(it));
489 let from_prelude = self.resolve_in_prelude(db, name);
490
491 from_legacy_macro.or(from_scope).or(from_extern_prelude).or(from_prelude)
492 }
493
494 fn resolve_name_in_extern_prelude(&self, name: &Name) -> PerNs {
495 self.extern_prelude.get(name).map_or(PerNs::none(), |&it| PerNs::types(it))
496 }
497
498 fn resolve_in_prelude(&self, db: &impl DefDatabase, name: &Name) -> PerNs {
499 if let Some(prelude) = self.prelude {
500 let keep;
501 let def_map = if prelude.krate() == self.krate {
502 self
503 } else {
504 // Extend lifetime
505 keep = db.crate_def_map(prelude.krate());
506 &keep
507 };
508 def_map[prelude.id.module_id].scope.get(name).map_or_else(PerNs::none, |res| res.def)
509 } else {
510 PerNs::none()
511 }
512 }
513}
514
515mod diagnostics {
516 use hir_expand::diagnostics::DiagnosticSink;
517 use ra_syntax::{ast, AstPtr};
518 use relative_path::RelativePathBuf;
519
520 use crate::{
521 db::{AstDatabase, DefDatabase},
522 diagnostics::UnresolvedModule,
523 nameres::CrateModuleId,
524 AstId,
525 };
526
527 #[derive(Debug, PartialEq, Eq)]
528 pub(super) enum DefDiagnostic {
529 UnresolvedModule {
530 module: CrateModuleId,
531 declaration: AstId<ast::Module>,
532 candidate: RelativePathBuf,
533 },
534 }
535
536 impl DefDiagnostic {
537 pub(super) fn add_to(
538 &self,
539 db: &(impl DefDatabase + AstDatabase),
540 target_module: CrateModuleId,
541 sink: &mut DiagnosticSink,
542 ) {
543 match self {
544 DefDiagnostic::UnresolvedModule { module, declaration, candidate } => {
545 if *module != target_module {
546 return;
547 }
548 let decl = declaration.to_node(db);
549 sink.push(UnresolvedModule {
550 file: declaration.file_id(),
551 decl: AstPtr::new(&decl),
552 candidate: candidate.clone(),
553 })
554 }
555 }
556 }
557 }
558}
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-03 09:23:50 +0000