1 //! This module implements import-resolution/macro expansion algorithm.
3 //! The result of this module is `CrateDefMap`: a data structure which contains:
5 //! * a tree of modules for the crate
6 //! * for each module, a set of items visible in the module (directly declared
9 //! Note that `CrateDefMap` contains fully macro expanded code.
11 //! Computing `CrateDefMap` can be partitioned into several logically
12 //! independent "phases". The phases are mutually recursive though, there's no
15 //! ## Collecting RawItems
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 this
19 //! phase. Macro calls are represented as a triple of (Path, Option<Name>,
22 //! ## Collecting Modules
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.
29 //! While we walk tree of modules, we also record macro_rules definitions and
30 //! expand calls to macro_rules defined macros.
32 //! ## Resolving Imports
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.
39 //! ## Resolving Macros
41 //! macro_rules from the same crate use a global mutable namespace. We expand
42 //! them immediately, when we collect modules.
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 on
60 use base_db::{CrateId, Edition, FileId};
61 use hir_expand::{diagnostics::DiagnosticSink, name::Name, InFile, MacroDefId};
64 use rustc_hash::FxHashMap;
70 item_scope::{BuiltinShadowMode, ItemScope},
71 nameres::{diagnostics::DefDiagnostic, path_resolution::ResolveMode},
74 AstId, BlockId, BlockLoc, LocalModuleId, ModuleDefId, ModuleId,
77 use self::proc_macro::ProcMacroDef;
79 /// Contains the results of (early) name resolution.
81 /// A `DefMap` stores the module tree and the definitions that are in scope in every module after
82 /// item-level macros have been expanded.
84 /// Every crate has a primary `DefMap` whose root is the crate's main file (`main.rs`/`lib.rs`),
85 /// computed by the `crate_def_map` query. Additionally, every block expression introduces the
86 /// opportunity to write arbitrary item and module hierarchies, and thus gets its own `DefMap` that
87 /// is computed by the `block_def_map` query.
88 #[derive(Debug, PartialEq, Eq)]
91 block: Option<BlockInfo>,
93 modules: Arena<ModuleData>,
95 /// The prelude module for this crate. This either comes from an import
96 /// marked with the `prelude_import` attribute, or (in the normal case) from
97 /// a dependency (`std` or `core`).
98 prelude: Option<ModuleId>,
99 extern_prelude: FxHashMap<Name, ModuleDefId>,
101 /// Side table with additional proc. macro info, for use by name resolution in downstream
104 /// (the primary purpose is to resolve derive helpers)
105 exported_proc_macros: FxHashMap<MacroDefId, ProcMacroDef>,
108 diagnostics: Vec<DefDiagnostic>,
111 /// For `DefMap`s computed for a block expression, this stores its location in the parent map.
112 #[derive(Debug, PartialEq, Eq, Clone, Copy)]
114 /// The `BlockId` this `DefMap` was created from.
116 /// The containing module.
120 impl std::ops::Index<LocalModuleId> for DefMap {
121 type Output = ModuleData;
122 fn index(&self, id: LocalModuleId) -> &ModuleData {
127 #[derive(Debug, PartialEq, Eq, Clone, Copy, Hash)]
128 pub enum ModuleOrigin {
132 /// Note that non-inline modules, by definition, live inside non-macro file.
135 declaration: AstId<ast::Module>,
139 definition: AstId<ast::Module>,
141 /// Pseudo-module introduced by a block scope (contains only inner items).
143 block: AstId<ast::BlockExpr>,
147 impl Default for ModuleOrigin {
148 fn default() -> Self {
149 ModuleOrigin::CrateRoot { definition: FileId(0) }
154 fn declaration(&self) -> Option<AstId<ast::Module>> {
156 ModuleOrigin::File { declaration: module, .. }
157 | ModuleOrigin::Inline { definition: module, .. } => Some(*module),
158 ModuleOrigin::CrateRoot { .. } | ModuleOrigin::BlockExpr { .. } => None,
162 pub fn file_id(&self) -> Option<FileId> {
164 ModuleOrigin::File { definition, .. } | ModuleOrigin::CrateRoot { definition } => {
171 pub fn is_inline(&self) -> bool {
173 ModuleOrigin::Inline { .. } | ModuleOrigin::BlockExpr { .. } => true,
174 ModuleOrigin::CrateRoot { .. } | ModuleOrigin::File { .. } => false,
178 /// Returns a node which defines this module.
179 /// That is, a file or a `mod foo {}` with items.
180 fn definition_source(&self, db: &dyn DefDatabase) -> InFile<ModuleSource> {
182 ModuleOrigin::File { definition, .. } | ModuleOrigin::CrateRoot { definition } => {
183 let file_id = *definition;
184 let sf = db.parse(file_id).tree();
185 InFile::new(file_id.into(), ModuleSource::SourceFile(sf))
187 ModuleOrigin::Inline { definition } => InFile::new(
189 ModuleSource::Module(definition.to_node(db.upcast())),
191 ModuleOrigin::BlockExpr { block } => {
192 InFile::new(block.file_id, ModuleSource::BlockExpr(block.to_node(db.upcast())))
198 #[derive(Default, Debug, PartialEq, Eq)]
199 pub struct ModuleData {
200 pub parent: Option<LocalModuleId>,
201 pub children: FxHashMap<Name, LocalModuleId>,
202 pub scope: ItemScope,
204 /// Where does this module come from?
205 pub origin: ModuleOrigin,
209 pub(crate) fn crate_def_map_query(db: &dyn DefDatabase, krate: CrateId) -> Arc<DefMap> {
210 let _p = profile::span("crate_def_map_query").detail(|| {
211 db.crate_graph()[krate].display_name.as_deref().unwrap_or_default().to_string()
213 let edition = db.crate_graph()[krate].edition;
214 let def_map = DefMap::empty(krate, edition);
215 let def_map = collector::collect_defs(db, def_map, None);
219 pub(crate) fn block_def_map_query(
220 db: &dyn DefDatabase,
222 ) -> Option<Arc<DefMap>> {
223 let block: BlockLoc = db.lookup_intern_block(block_id);
225 let item_tree = db.file_item_tree(block.ast_id.file_id);
226 if item_tree.inner_items_of_block(block.ast_id.value).is_empty() {
230 let block_info = BlockInfo { block: block_id, parent: block.module };
232 let parent_map = block.module.def_map(db);
233 let mut def_map = DefMap::empty(block.module.krate, parent_map.edition);
234 def_map.block = Some(block_info);
236 let def_map = collector::collect_defs(db, def_map, Some(block.ast_id));
237 Some(Arc::new(def_map))
240 fn empty(krate: CrateId, edition: Edition) -> DefMap {
241 let mut modules: Arena<ModuleData> = Arena::default();
242 let root = modules.alloc(ModuleData::default());
248 extern_prelude: FxHashMap::default(),
249 exported_proc_macros: FxHashMap::default(),
253 diagnostics: Vec::new(),
257 pub fn add_diagnostics(
259 db: &dyn DefDatabase,
260 module: LocalModuleId,
261 sink: &mut DiagnosticSink,
263 self.diagnostics.iter().for_each(|it| it.add_to(db, module, sink))
266 pub fn modules_for_file(&self, file_id: FileId) -> impl Iterator<Item = LocalModuleId> + '_ {
269 .filter(move |(_id, data)| data.origin.file_id() == Some(file_id))
270 .map(|(id, _data)| id)
273 pub fn modules(&self) -> impl Iterator<Item = (LocalModuleId, &ModuleData)> + '_ {
277 pub fn root(&self) -> LocalModuleId {
281 pub(crate) fn krate(&self) -> CrateId {
285 pub(crate) fn block_id(&self) -> Option<BlockId> {
286 self.block.as_ref().map(|block| block.block)
289 pub(crate) fn prelude(&self) -> Option<ModuleId> {
293 pub(crate) fn extern_prelude(&self) -> impl Iterator<Item = (&Name, &ModuleDefId)> + '_ {
294 self.extern_prelude.iter()
297 pub fn module_id(&self, local_id: LocalModuleId) -> ModuleId {
298 let block = self.block.as_ref().map(|b| b.block);
299 ModuleId { krate: self.krate, local_id, block }
302 pub(crate) fn crate_root(&self, db: &dyn DefDatabase) -> ModuleId {
303 self.with_ancestor_maps(db, self.root, &mut |def_map, _module| {
304 if def_map.block.is_none() {
305 Some(def_map.module_id(def_map.root))
310 .expect("DefMap chain without root")
313 pub(crate) fn resolve_path(
315 db: &dyn DefDatabase,
316 original_module: LocalModuleId,
318 shadow: BuiltinShadowMode,
319 ) -> (PerNs, Option<usize>) {
321 self.resolve_path_fp_with_macro(db, ResolveMode::Other, original_module, path, shadow);
322 (res.resolved_def, res.segment_index)
325 pub(crate) fn resolve_path_locally(
327 db: &dyn DefDatabase,
328 original_module: LocalModuleId,
330 shadow: BuiltinShadowMode,
331 ) -> (PerNs, Option<usize>) {
332 let res = self.resolve_path_fp_with_macro_single(
339 (res.resolved_def, res.segment_index)
342 /// Ascends the `DefMap` hierarchy and calls `f` with every `DefMap` and containing module.
344 /// If `f` returns `Some(val)`, iteration is stopped and `Some(val)` is returned. If `f` returns
345 /// `None`, iteration continues.
346 pub fn with_ancestor_maps<T>(
348 db: &dyn DefDatabase,
349 local_mod: LocalModuleId,
350 f: &mut dyn FnMut(&DefMap, LocalModuleId) -> Option<T>,
352 if let Some(it) = f(self, local_mod) {
355 let mut block = self.block;
356 while let Some(block_info) = block {
357 let parent = block_info.parent.def_map(db);
358 if let Some(it) = f(&parent, block_info.parent.local_id) {
361 block = parent.block;
367 /// If this `DefMap` is for a block expression, returns the module containing the block (which
368 /// might again be a block, or a module inside a block).
369 pub fn parent(&self) -> Option<ModuleId> {
370 Some(self.block?.parent)
373 /// Returns the module containing `local_mod`, either the parent `mod`, or the module containing
374 /// the block, if `self` corresponds to a block expression.
375 pub fn containing_module(&self, local_mod: LocalModuleId) -> Option<ModuleId> {
376 match &self[local_mod].parent {
377 Some(parent) => Some(self.module_id(*parent)),
378 None => match &self.block {
379 Some(block) => Some(block.parent),
385 // FIXME: this can use some more human-readable format (ideally, an IR
386 // even), as this should be a great debugging aid.
387 pub fn dump(&self, db: &dyn DefDatabase) -> String {
388 let mut buf = String::new();
390 let mut current_map = self;
391 while let Some(block) = ¤t_map.block {
392 go(&mut buf, current_map, "block scope", current_map.root);
394 arc = block.parent.def_map(db);
397 go(&mut buf, current_map, "crate", current_map.root);
400 fn go(buf: &mut String, map: &DefMap, path: &str, module: LocalModuleId) {
401 format_to!(buf, "{}\n", path);
403 map.modules[module].scope.dump(buf);
405 for (name, child) in map.modules[module].children.iter() {
406 let path = format!("{}::{}", path, name);
408 go(buf, map, &path, *child);
413 pub fn dump_block_scopes(&self, db: &dyn DefDatabase) -> String {
414 let mut buf = String::new();
416 let mut current_map = self;
417 while let Some(block) = ¤t_map.block {
418 format_to!(buf, "{:?} in {:?}\n", block.block, block.parent);
419 arc = block.parent.def_map(db);
423 format_to!(buf, "crate scope\n");
427 fn shrink_to_fit(&mut self) {
428 // Exhaustive match to require handling new fields.
431 exported_proc_macros,
442 extern_prelude.shrink_to_fit();
443 exported_proc_macros.shrink_to_fit();
444 diagnostics.shrink_to_fit();
445 modules.shrink_to_fit();
446 for (_, module) in modules.iter_mut() {
447 module.children.shrink_to_fit();
448 module.scope.shrink_to_fit();
454 /// Returns a node which defines this module. That is, a file or a `mod foo {}` with items.
455 pub fn definition_source(&self, db: &dyn DefDatabase) -> InFile<ModuleSource> {
456 self.origin.definition_source(db)
459 /// Returns a node which declares this module, either a `mod foo;` or a `mod foo {}`.
460 /// `None` for the crate root or block.
461 pub fn declaration_source(&self, db: &dyn DefDatabase) -> Option<InFile<ast::Module>> {
462 let decl = self.origin.declaration()?;
463 let value = decl.to_node(db.upcast());
464 Some(InFile { file_id: decl.file_id, value })
468 #[derive(Debug, Clone, PartialEq, Eq)]
469 pub enum ModuleSource {
470 SourceFile(ast::SourceFile),
472 BlockExpr(ast::BlockExpr),
476 use cfg::{CfgExpr, CfgOptions};
477 use hir_expand::diagnostics::DiagnosticSink;
478 use hir_expand::hygiene::Hygiene;
479 use hir_expand::{InFile, MacroCallKind};
480 use syntax::ast::AttrsOwner;
481 use syntax::{ast, AstNode, AstPtr, SyntaxKind, SyntaxNodePtr};
483 use crate::path::ModPath;
484 use crate::{db::DefDatabase, diagnostics::*, nameres::LocalModuleId, AstId};
486 #[derive(Debug, PartialEq, Eq)]
487 enum DiagnosticKind {
488 UnresolvedModule { declaration: AstId<ast::Module>, candidate: String },
490 UnresolvedExternCrate { ast: AstId<ast::ExternCrate> },
492 UnresolvedImport { ast: AstId<ast::Use>, index: usize },
494 UnconfiguredCode { ast: AstId<ast::Item>, cfg: CfgExpr, opts: CfgOptions },
496 UnresolvedProcMacro { ast: MacroCallKind },
498 UnresolvedMacroCall { ast: AstId<ast::MacroCall>, path: ModPath },
500 MacroError { ast: MacroCallKind, message: String },
503 #[derive(Debug, PartialEq, Eq)]
504 pub(super) struct DefDiagnostic {
505 in_module: LocalModuleId,
506 kind: DiagnosticKind,
510 pub(super) fn unresolved_module(
511 container: LocalModuleId,
512 declaration: AstId<ast::Module>,
516 in_module: container,
517 kind: DiagnosticKind::UnresolvedModule { declaration, candidate },
521 pub(super) fn unresolved_extern_crate(
522 container: LocalModuleId,
523 declaration: AstId<ast::ExternCrate>,
526 in_module: container,
527 kind: DiagnosticKind::UnresolvedExternCrate { ast: declaration },
531 pub(super) fn unresolved_import(
532 container: LocalModuleId,
533 ast: AstId<ast::Use>,
536 Self { in_module: container, kind: DiagnosticKind::UnresolvedImport { ast, index } }
539 pub(super) fn unconfigured_code(
540 container: LocalModuleId,
541 ast: AstId<ast::Item>,
545 Self { in_module: container, kind: DiagnosticKind::UnconfiguredCode { ast, cfg, opts } }
548 pub(super) fn unresolved_proc_macro(container: LocalModuleId, ast: MacroCallKind) -> Self {
549 Self { in_module: container, kind: DiagnosticKind::UnresolvedProcMacro { ast } }
552 pub(super) fn macro_error(
553 container: LocalModuleId,
557 Self { in_module: container, kind: DiagnosticKind::MacroError { ast, message } }
560 pub(super) fn unresolved_macro_call(
561 container: LocalModuleId,
562 ast: AstId<ast::MacroCall>,
565 Self { in_module: container, kind: DiagnosticKind::UnresolvedMacroCall { ast, path } }
568 pub(super) fn add_to(
570 db: &dyn DefDatabase,
571 target_module: LocalModuleId,
572 sink: &mut DiagnosticSink,
574 if self.in_module != target_module {
579 DiagnosticKind::UnresolvedModule { declaration, candidate } => {
580 let decl = declaration.to_node(db.upcast());
581 sink.push(UnresolvedModule {
582 file: declaration.file_id,
583 decl: AstPtr::new(&decl),
584 candidate: candidate.clone(),
588 DiagnosticKind::UnresolvedExternCrate { ast } => {
589 let item = ast.to_node(db.upcast());
590 sink.push(UnresolvedExternCrate {
592 item: AstPtr::new(&item),
596 DiagnosticKind::UnresolvedImport { ast, index } => {
597 let use_item = ast.to_node(db.upcast());
598 let hygiene = Hygiene::new(db.upcast(), ast.file_id);
601 ModPath::expand_use_item(
602 InFile::new(ast.file_id, use_item),
604 |_mod_path, use_tree, _is_glob, _alias| {
606 tree = Some(use_tree.clone());
613 if let Some(tree) = tree {
614 sink.push(UnresolvedImport { file: ast.file_id, node: AstPtr::new(&tree) });
618 DiagnosticKind::UnconfiguredCode { ast, cfg, opts } => {
619 let item = ast.to_node(db.upcast());
620 sink.push(InactiveCode {
622 node: AstPtr::new(&item).into(),
628 DiagnosticKind::UnresolvedProcMacro { ast } => {
629 let mut precise_location = None;
630 let (file, ast, name) = match ast {
631 MacroCallKind::FnLike { ast_id } => {
632 let node = ast_id.to_node(db.upcast());
633 (ast_id.file_id, SyntaxNodePtr::from(AstPtr::new(&node)), None)
635 MacroCallKind::Derive { ast_id, derive_name, .. } => {
636 let node = ast_id.to_node(db.upcast());
638 // Compute the precise location of the macro name's token in the derive
640 // FIXME: This does not handle paths to the macro, but neither does the
643 node.attrs().filter_map(|attr| match attr.as_simple_call() {
644 Some((name, args)) if name == "derive" => Some(args),
647 'outer: for attr in derive_attrs {
649 attr.syntax().children_with_tokens().filter_map(|elem| {
651 syntax::NodeOrToken::Node(_) => None,
652 syntax::NodeOrToken::Token(tok) => Some(tok),
655 for token in tokens {
656 if token.kind() == SyntaxKind::IDENT
657 && token.text() == derive_name.as_str()
659 precise_location = Some(token.text_range());
667 SyntaxNodePtr::from(AstPtr::new(&node)),
668 Some(derive_name.clone()),
672 sink.push(UnresolvedProcMacro {
680 DiagnosticKind::UnresolvedMacroCall { ast, path } => {
681 let node = ast.to_node(db.upcast());
682 sink.push(UnresolvedMacroCall {
684 node: AstPtr::new(&node),
689 DiagnosticKind::MacroError { ast, message } => {
690 let (file, ast) = match ast {
691 MacroCallKind::FnLike { ast_id, .. } => {
692 let node = ast_id.to_node(db.upcast());
693 (ast_id.file_id, SyntaxNodePtr::from(AstPtr::new(&node)))
695 MacroCallKind::Derive { ast_id, .. } => {
696 let node = ast_id.to_node(db.upcast());
697 (ast_id.file_id, SyntaxNodePtr::from(AstPtr::new(&node)))
700 sink.push(MacroError { file, node: ast, message: message.clone() });