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};
62 use rustc_hash::FxHashMap;
68 item_scope::{BuiltinShadowMode, ItemScope},
69 nameres::{diagnostics::DefDiagnostic, path_resolution::ResolveMode},
72 AstId, LocalModuleId, ModuleDefId, ModuleId,
75 /// Contains all top-level defs from a macro-expanded crate
76 #[derive(Debug, PartialEq, Eq)]
77 pub struct CrateDefMap {
78 pub root: LocalModuleId,
79 pub modules: Arena<ModuleData>,
80 pub(crate) krate: CrateId,
81 /// The prelude module for this crate. This either comes from an import
82 /// marked with the `prelude_import` attribute, or (in the normal case) from
83 /// a dependency (`std` or `core`).
84 pub(crate) prelude: Option<ModuleId>,
85 pub(crate) extern_prelude: FxHashMap<Name, ModuleDefId>,
88 diagnostics: Vec<DefDiagnostic>,
91 impl std::ops::Index<LocalModuleId> for CrateDefMap {
92 type Output = ModuleData;
93 fn index(&self, id: LocalModuleId) -> &ModuleData {
98 #[derive(Debug, PartialEq, Eq, Clone, Copy, Hash)]
99 pub enum ModuleOrigin {
103 /// Note that non-inline modules, by definition, live inside non-macro file.
106 declaration: AstId<ast::Module>,
110 definition: AstId<ast::Module>,
114 impl Default for ModuleOrigin {
115 fn default() -> Self {
116 ModuleOrigin::CrateRoot { definition: FileId(0) }
121 fn declaration(&self) -> Option<AstId<ast::Module>> {
123 ModuleOrigin::File { declaration: module, .. }
124 | ModuleOrigin::Inline { definition: module, .. } => Some(*module),
125 ModuleOrigin::CrateRoot { .. } => None,
129 pub fn file_id(&self) -> Option<FileId> {
131 ModuleOrigin::File { definition, .. } | ModuleOrigin::CrateRoot { definition } => {
138 pub fn is_inline(&self) -> bool {
140 ModuleOrigin::Inline { .. } => true,
141 ModuleOrigin::CrateRoot { .. } | ModuleOrigin::File { .. } => false,
145 /// Returns a node which defines this module.
146 /// That is, a file or a `mod foo {}` with items.
147 fn definition_source(&self, db: &dyn DefDatabase) -> InFile<ModuleSource> {
149 ModuleOrigin::File { definition, .. } | ModuleOrigin::CrateRoot { definition } => {
150 let file_id = *definition;
151 let sf = db.parse(file_id).tree();
152 InFile::new(file_id.into(), ModuleSource::SourceFile(sf))
154 ModuleOrigin::Inline { definition } => InFile::new(
156 ModuleSource::Module(definition.to_node(db.upcast())),
162 #[derive(Default, Debug, PartialEq, Eq)]
163 pub struct ModuleData {
164 pub parent: Option<LocalModuleId>,
165 pub children: FxHashMap<Name, LocalModuleId>,
166 pub scope: ItemScope,
168 /// Where does this module come from?
169 pub origin: ModuleOrigin,
173 pub(crate) fn crate_def_map_query(db: &dyn DefDatabase, krate: CrateId) -> Arc<CrateDefMap> {
174 let _p = profile::span("crate_def_map_query").detail(|| {
175 db.crate_graph()[krate].display_name.as_deref().unwrap_or_default().to_string()
178 let edition = db.crate_graph()[krate].edition;
179 let mut modules: Arena<ModuleData> = Arena::default();
180 let root = modules.alloc(ModuleData::default());
184 extern_prelude: FxHashMap::default(),
188 diagnostics: Vec::new(),
191 let def_map = collector::collect_defs(db, def_map);
195 pub fn add_diagnostics(
197 db: &dyn DefDatabase,
198 module: LocalModuleId,
199 sink: &mut DiagnosticSink,
201 self.diagnostics.iter().for_each(|it| it.add_to(db, module, sink))
204 pub fn modules_for_file(&self, file_id: FileId) -> impl Iterator<Item = LocalModuleId> + '_ {
207 .filter(move |(_id, data)| data.origin.file_id() == Some(file_id))
208 .map(|(id, _data)| id)
211 pub(crate) fn resolve_path(
213 db: &dyn DefDatabase,
214 original_module: LocalModuleId,
216 shadow: BuiltinShadowMode,
217 ) -> (PerNs, Option<usize>) {
219 self.resolve_path_fp_with_macro(db, ResolveMode::Other, original_module, path, shadow);
220 (res.resolved_def, res.segment_index)
223 // FIXME: this can use some more human-readable format (ideally, an IR
224 // even), as this should be a great debugging aid.
225 pub fn dump(&self) -> String {
226 let mut buf = String::new();
227 go(&mut buf, self, "crate", self.root);
230 fn go(buf: &mut String, map: &CrateDefMap, path: &str, module: LocalModuleId) {
231 format_to!(buf, "{}\n", path);
233 let mut entries: Vec<_> = map.modules[module].scope.resolutions().collect();
234 entries.sort_by_key(|(name, _)| name.clone());
236 for (name, def) in entries {
237 format_to!(buf, "{}:", name.map_or("_".to_string(), |name| name.to_string()));
239 if def.types.is_some() {
242 if def.values.is_some() {
245 if def.macros.is_some() {
255 for (name, child) in map.modules[module].children.iter() {
256 let path = format!("{}::{}", path, name);
258 go(buf, map, &path, *child);
265 /// Returns a node which defines this module. That is, a file or a `mod foo {}` with items.
266 pub fn definition_source(&self, db: &dyn DefDatabase) -> InFile<ModuleSource> {
267 self.origin.definition_source(db)
270 /// Returns a node which declares this module, either a `mod foo;` or a `mod foo {}`.
271 /// `None` for the crate root or block.
272 pub fn declaration_source(&self, db: &dyn DefDatabase) -> Option<InFile<ast::Module>> {
273 let decl = self.origin.declaration()?;
274 let value = decl.to_node(db.upcast());
275 Some(InFile { file_id: decl.file_id, value })
279 #[derive(Debug, Clone, PartialEq, Eq)]
280 pub enum ModuleSource {
281 SourceFile(ast::SourceFile),
286 use cfg::{CfgExpr, CfgOptions};
287 use hir_expand::diagnostics::DiagnosticSink;
288 use hir_expand::hygiene::Hygiene;
289 use hir_expand::InFile;
290 use syntax::{ast, AstPtr};
292 use crate::path::ModPath;
293 use crate::{db::DefDatabase, diagnostics::*, nameres::LocalModuleId, AstId};
295 #[derive(Debug, PartialEq, Eq)]
296 enum DiagnosticKind {
297 UnresolvedModule { declaration: AstId<ast::Module>, candidate: String },
299 UnresolvedExternCrate { ast: AstId<ast::ExternCrate> },
301 UnresolvedImport { ast: AstId<ast::Use>, index: usize },
303 UnconfiguredCode { ast: AstId<ast::Item>, cfg: CfgExpr, opts: CfgOptions },
306 #[derive(Debug, PartialEq, Eq)]
307 pub(super) struct DefDiagnostic {
308 in_module: LocalModuleId,
309 kind: DiagnosticKind,
313 pub(super) fn unresolved_module(
314 container: LocalModuleId,
315 declaration: AstId<ast::Module>,
319 in_module: container,
320 kind: DiagnosticKind::UnresolvedModule { declaration, candidate },
324 pub(super) fn unresolved_extern_crate(
325 container: LocalModuleId,
326 declaration: AstId<ast::ExternCrate>,
329 in_module: container,
330 kind: DiagnosticKind::UnresolvedExternCrate { ast: declaration },
334 pub(super) fn unresolved_import(
335 container: LocalModuleId,
336 ast: AstId<ast::Use>,
339 Self { in_module: container, kind: DiagnosticKind::UnresolvedImport { ast, index } }
342 pub(super) fn unconfigured_code(
343 container: LocalModuleId,
344 ast: AstId<ast::Item>,
348 Self { in_module: container, kind: DiagnosticKind::UnconfiguredCode { ast, cfg, opts } }
351 pub(super) fn add_to(
353 db: &dyn DefDatabase,
354 target_module: LocalModuleId,
355 sink: &mut DiagnosticSink,
357 if self.in_module != target_module {
362 DiagnosticKind::UnresolvedModule { declaration, candidate } => {
363 let decl = declaration.to_node(db.upcast());
364 sink.push(UnresolvedModule {
365 file: declaration.file_id,
366 decl: AstPtr::new(&decl),
367 candidate: candidate.clone(),
371 DiagnosticKind::UnresolvedExternCrate { ast } => {
372 let item = ast.to_node(db.upcast());
373 sink.push(UnresolvedExternCrate {
375 item: AstPtr::new(&item),
379 DiagnosticKind::UnresolvedImport { ast, index } => {
380 let use_item = ast.to_node(db.upcast());
381 let hygiene = Hygiene::new(db.upcast(), ast.file_id);
384 ModPath::expand_use_item(
385 InFile::new(ast.file_id, use_item),
387 |_mod_path, use_tree, _is_glob, _alias| {
389 tree = Some(use_tree.clone());
396 if let Some(tree) = tree {
397 sink.push(UnresolvedImport { file: ast.file_id, node: AstPtr::new(&tree) });
401 DiagnosticKind::UnconfiguredCode { ast, cfg, opts } => {
402 let item = ast.to_node(db.upcast());
403 sink.push(InactiveCode {
405 node: AstPtr::new(&item).into(),