]> git.lizzy.rs Git - rust.git/blob - crates/hir_def/src/nameres.rs
Merge #8443 #8446
[rust.git] / crates / hir_def / src / nameres.rs
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 this
19 //! 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 on
48 //! the result
49
50 mod collector;
51 mod mod_resolution;
52 mod path_resolution;
53
54 #[cfg(test)]
55 mod tests;
56 mod proc_macro;
57
58 use std::sync::Arc;
59
60 use base_db::{CrateId, Edition, FileId};
61 use hir_expand::{diagnostics::DiagnosticSink, name::Name, InFile, MacroDefId};
62 use la_arena::Arena;
63 use profile::Count;
64 use rustc_hash::FxHashMap;
65 use stdx::format_to;
66 use syntax::ast;
67
68 use crate::{
69     db::DefDatabase,
70     item_scope::{BuiltinShadowMode, ItemScope},
71     nameres::{diagnostics::DefDiagnostic, path_resolution::ResolveMode},
72     path::ModPath,
73     per_ns::PerNs,
74     AstId, BlockId, BlockLoc, LocalModuleId, ModuleDefId, ModuleId,
75 };
76
77 use self::proc_macro::ProcMacroDef;
78
79 /// Contains the results of (early) name resolution.
80 ///
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.
83 ///
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)]
89 pub struct DefMap {
90     _c: Count<Self>,
91     block: Option<BlockInfo>,
92     root: LocalModuleId,
93     modules: Arena<ModuleData>,
94     krate: CrateId,
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>,
100
101     /// Side table with additional proc. macro info, for use by name resolution in downstream
102     /// crates.
103     ///
104     /// (the primary purpose is to resolve derive helpers)
105     exported_proc_macros: FxHashMap<MacroDefId, ProcMacroDef>,
106
107     edition: Edition,
108     diagnostics: Vec<DefDiagnostic>,
109 }
110
111 /// For `DefMap`s computed for a block expression, this stores its location in the parent map.
112 #[derive(Debug, PartialEq, Eq, Clone, Copy)]
113 struct BlockInfo {
114     /// The `BlockId` this `DefMap` was created from.
115     block: BlockId,
116     /// The containing module.
117     parent: ModuleId,
118 }
119
120 impl std::ops::Index<LocalModuleId> for DefMap {
121     type Output = ModuleData;
122     fn index(&self, id: LocalModuleId) -> &ModuleData {
123         &self.modules[id]
124     }
125 }
126
127 #[derive(Debug, PartialEq, Eq, Clone, Copy, Hash)]
128 pub enum ModuleOrigin {
129     CrateRoot {
130         definition: FileId,
131     },
132     /// Note that non-inline modules, by definition, live inside non-macro file.
133     File {
134         is_mod_rs: bool,
135         declaration: AstId<ast::Module>,
136         definition: FileId,
137     },
138     Inline {
139         definition: AstId<ast::Module>,
140     },
141     /// Pseudo-module introduced by a block scope (contains only inner items).
142     BlockExpr {
143         block: AstId<ast::BlockExpr>,
144     },
145 }
146
147 impl Default for ModuleOrigin {
148     fn default() -> Self {
149         ModuleOrigin::CrateRoot { definition: FileId(0) }
150     }
151 }
152
153 impl ModuleOrigin {
154     fn declaration(&self) -> Option<AstId<ast::Module>> {
155         match self {
156             ModuleOrigin::File { declaration: module, .. }
157             | ModuleOrigin::Inline { definition: module, .. } => Some(*module),
158             ModuleOrigin::CrateRoot { .. } | ModuleOrigin::BlockExpr { .. } => None,
159         }
160     }
161
162     pub fn file_id(&self) -> Option<FileId> {
163         match self {
164             ModuleOrigin::File { definition, .. } | ModuleOrigin::CrateRoot { definition } => {
165                 Some(*definition)
166             }
167             _ => None,
168         }
169     }
170
171     pub fn is_inline(&self) -> bool {
172         match self {
173             ModuleOrigin::Inline { .. } | ModuleOrigin::BlockExpr { .. } => true,
174             ModuleOrigin::CrateRoot { .. } | ModuleOrigin::File { .. } => false,
175         }
176     }
177
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> {
181         match self {
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))
186             }
187             ModuleOrigin::Inline { definition } => InFile::new(
188                 definition.file_id,
189                 ModuleSource::Module(definition.to_node(db.upcast())),
190             ),
191             ModuleOrigin::BlockExpr { block } => {
192                 InFile::new(block.file_id, ModuleSource::BlockExpr(block.to_node(db.upcast())))
193             }
194         }
195     }
196 }
197
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,
203
204     /// Where does this module come from?
205     pub origin: ModuleOrigin,
206 }
207
208 impl DefMap {
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()
212         });
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);
216         Arc::new(def_map)
217     }
218
219     pub(crate) fn block_def_map_query(
220         db: &dyn DefDatabase,
221         block_id: BlockId,
222     ) -> Option<Arc<DefMap>> {
223         let block: BlockLoc = db.lookup_intern_block(block_id);
224
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() {
227             return None;
228         }
229
230         let block_info = BlockInfo { block: block_id, parent: block.module };
231
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);
235
236         let def_map = collector::collect_defs(db, def_map, Some(block.ast_id));
237         Some(Arc::new(def_map))
238     }
239
240     fn empty(krate: CrateId, edition: Edition) -> DefMap {
241         let mut modules: Arena<ModuleData> = Arena::default();
242         let root = modules.alloc(ModuleData::default());
243         DefMap {
244             _c: Count::new(),
245             block: None,
246             krate,
247             edition,
248             extern_prelude: FxHashMap::default(),
249             exported_proc_macros: FxHashMap::default(),
250             prelude: None,
251             root,
252             modules,
253             diagnostics: Vec::new(),
254         }
255     }
256
257     pub fn add_diagnostics(
258         &self,
259         db: &dyn DefDatabase,
260         module: LocalModuleId,
261         sink: &mut DiagnosticSink,
262     ) {
263         self.diagnostics.iter().for_each(|it| it.add_to(db, module, sink))
264     }
265
266     pub fn modules_for_file(&self, file_id: FileId) -> impl Iterator<Item = LocalModuleId> + '_ {
267         self.modules
268             .iter()
269             .filter(move |(_id, data)| data.origin.file_id() == Some(file_id))
270             .map(|(id, _data)| id)
271     }
272
273     pub fn modules(&self) -> impl Iterator<Item = (LocalModuleId, &ModuleData)> + '_ {
274         self.modules.iter()
275     }
276
277     pub fn root(&self) -> LocalModuleId {
278         self.root
279     }
280
281     pub(crate) fn krate(&self) -> CrateId {
282         self.krate
283     }
284
285     pub(crate) fn block_id(&self) -> Option<BlockId> {
286         self.block.as_ref().map(|block| block.block)
287     }
288
289     pub(crate) fn prelude(&self) -> Option<ModuleId> {
290         self.prelude
291     }
292
293     pub(crate) fn extern_prelude(&self) -> impl Iterator<Item = (&Name, &ModuleDefId)> + '_ {
294         self.extern_prelude.iter()
295     }
296
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 }
300     }
301
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))
306             } else {
307                 None
308             }
309         })
310         .expect("DefMap chain without root")
311     }
312
313     pub(crate) fn resolve_path(
314         &self,
315         db: &dyn DefDatabase,
316         original_module: LocalModuleId,
317         path: &ModPath,
318         shadow: BuiltinShadowMode,
319     ) -> (PerNs, Option<usize>) {
320         let res =
321             self.resolve_path_fp_with_macro(db, ResolveMode::Other, original_module, path, shadow);
322         (res.resolved_def, res.segment_index)
323     }
324
325     pub(crate) fn resolve_path_locally(
326         &self,
327         db: &dyn DefDatabase,
328         original_module: LocalModuleId,
329         path: &ModPath,
330         shadow: BuiltinShadowMode,
331     ) -> (PerNs, Option<usize>) {
332         let res = self.resolve_path_fp_with_macro_single(
333             db,
334             ResolveMode::Other,
335             original_module,
336             path,
337             shadow,
338         );
339         (res.resolved_def, res.segment_index)
340     }
341
342     /// Ascends the `DefMap` hierarchy and calls `f` with every `DefMap` and containing module.
343     ///
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>(
347         &self,
348         db: &dyn DefDatabase,
349         local_mod: LocalModuleId,
350         f: &mut dyn FnMut(&DefMap, LocalModuleId) -> Option<T>,
351     ) -> Option<T> {
352         if let Some(it) = f(self, local_mod) {
353             return Some(it);
354         }
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) {
359                 return Some(it);
360             }
361             block = parent.block;
362         }
363
364         None
365     }
366
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)
371     }
372
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),
380                 None => None,
381             },
382         }
383     }
384
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();
389         let mut arc;
390         let mut current_map = self;
391         while let Some(block) = &current_map.block {
392             go(&mut buf, current_map, "block scope", current_map.root);
393             buf.push('\n');
394             arc = block.parent.def_map(db);
395             current_map = &*arc;
396         }
397         go(&mut buf, current_map, "crate", current_map.root);
398         return buf;
399
400         fn go(buf: &mut String, map: &DefMap, path: &str, module: LocalModuleId) {
401             format_to!(buf, "{}\n", path);
402
403             map.modules[module].scope.dump(buf);
404
405             for (name, child) in map.modules[module].children.iter() {
406                 let path = format!("{}::{}", path, name);
407                 buf.push('\n');
408                 go(buf, map, &path, *child);
409             }
410         }
411     }
412
413     fn shrink_to_fit(&mut self) {
414         // Exhaustive match to require handling new fields.
415         let Self {
416             _c: _,
417             exported_proc_macros,
418             extern_prelude,
419             diagnostics,
420             modules,
421             block: _,
422             edition: _,
423             krate: _,
424             prelude: _,
425             root: _,
426         } = self;
427
428         extern_prelude.shrink_to_fit();
429         exported_proc_macros.shrink_to_fit();
430         diagnostics.shrink_to_fit();
431         modules.shrink_to_fit();
432         for (_, module) in modules.iter_mut() {
433             module.children.shrink_to_fit();
434             module.scope.shrink_to_fit();
435         }
436     }
437 }
438
439 impl ModuleData {
440     /// Returns a node which defines this module. That is, a file or a `mod foo {}` with items.
441     pub fn definition_source(&self, db: &dyn DefDatabase) -> InFile<ModuleSource> {
442         self.origin.definition_source(db)
443     }
444
445     /// Returns a node which declares this module, either a `mod foo;` or a `mod foo {}`.
446     /// `None` for the crate root or block.
447     pub fn declaration_source(&self, db: &dyn DefDatabase) -> Option<InFile<ast::Module>> {
448         let decl = self.origin.declaration()?;
449         let value = decl.to_node(db.upcast());
450         Some(InFile { file_id: decl.file_id, value })
451     }
452 }
453
454 #[derive(Debug, Clone, PartialEq, Eq)]
455 pub enum ModuleSource {
456     SourceFile(ast::SourceFile),
457     Module(ast::Module),
458     BlockExpr(ast::BlockExpr),
459 }
460
461 mod diagnostics {
462     use cfg::{CfgExpr, CfgOptions};
463     use hir_expand::diagnostics::DiagnosticSink;
464     use hir_expand::hygiene::Hygiene;
465     use hir_expand::{InFile, MacroCallKind};
466     use syntax::ast::AttrsOwner;
467     use syntax::{ast, AstNode, AstPtr, SyntaxKind, SyntaxNodePtr};
468
469     use crate::path::ModPath;
470     use crate::{db::DefDatabase, diagnostics::*, nameres::LocalModuleId, AstId};
471
472     #[derive(Debug, PartialEq, Eq)]
473     enum DiagnosticKind {
474         UnresolvedModule { declaration: AstId<ast::Module>, candidate: String },
475
476         UnresolvedExternCrate { ast: AstId<ast::ExternCrate> },
477
478         UnresolvedImport { ast: AstId<ast::Use>, index: usize },
479
480         UnconfiguredCode { ast: AstId<ast::Item>, cfg: CfgExpr, opts: CfgOptions },
481
482         UnresolvedProcMacro { ast: MacroCallKind },
483
484         UnresolvedMacroCall { ast: AstId<ast::MacroCall> },
485
486         MacroError { ast: MacroCallKind, message: String },
487     }
488
489     #[derive(Debug, PartialEq, Eq)]
490     pub(super) struct DefDiagnostic {
491         in_module: LocalModuleId,
492         kind: DiagnosticKind,
493     }
494
495     impl DefDiagnostic {
496         pub(super) fn unresolved_module(
497             container: LocalModuleId,
498             declaration: AstId<ast::Module>,
499             candidate: String,
500         ) -> Self {
501             Self {
502                 in_module: container,
503                 kind: DiagnosticKind::UnresolvedModule { declaration, candidate },
504             }
505         }
506
507         pub(super) fn unresolved_extern_crate(
508             container: LocalModuleId,
509             declaration: AstId<ast::ExternCrate>,
510         ) -> Self {
511             Self {
512                 in_module: container,
513                 kind: DiagnosticKind::UnresolvedExternCrate { ast: declaration },
514             }
515         }
516
517         pub(super) fn unresolved_import(
518             container: LocalModuleId,
519             ast: AstId<ast::Use>,
520             index: usize,
521         ) -> Self {
522             Self { in_module: container, kind: DiagnosticKind::UnresolvedImport { ast, index } }
523         }
524
525         pub(super) fn unconfigured_code(
526             container: LocalModuleId,
527             ast: AstId<ast::Item>,
528             cfg: CfgExpr,
529             opts: CfgOptions,
530         ) -> Self {
531             Self { in_module: container, kind: DiagnosticKind::UnconfiguredCode { ast, cfg, opts } }
532         }
533
534         pub(super) fn unresolved_proc_macro(container: LocalModuleId, ast: MacroCallKind) -> Self {
535             Self { in_module: container, kind: DiagnosticKind::UnresolvedProcMacro { ast } }
536         }
537
538         pub(super) fn macro_error(
539             container: LocalModuleId,
540             ast: MacroCallKind,
541             message: String,
542         ) -> Self {
543             Self { in_module: container, kind: DiagnosticKind::MacroError { ast, message } }
544         }
545
546         pub(super) fn unresolved_macro_call(
547             container: LocalModuleId,
548             ast: AstId<ast::MacroCall>,
549         ) -> Self {
550             Self { in_module: container, kind: DiagnosticKind::UnresolvedMacroCall { ast } }
551         }
552
553         pub(super) fn add_to(
554             &self,
555             db: &dyn DefDatabase,
556             target_module: LocalModuleId,
557             sink: &mut DiagnosticSink,
558         ) {
559             if self.in_module != target_module {
560                 return;
561             }
562
563             match &self.kind {
564                 DiagnosticKind::UnresolvedModule { declaration, candidate } => {
565                     let decl = declaration.to_node(db.upcast());
566                     sink.push(UnresolvedModule {
567                         file: declaration.file_id,
568                         decl: AstPtr::new(&decl),
569                         candidate: candidate.clone(),
570                     })
571                 }
572
573                 DiagnosticKind::UnresolvedExternCrate { ast } => {
574                     let item = ast.to_node(db.upcast());
575                     sink.push(UnresolvedExternCrate {
576                         file: ast.file_id,
577                         item: AstPtr::new(&item),
578                     });
579                 }
580
581                 DiagnosticKind::UnresolvedImport { ast, index } => {
582                     let use_item = ast.to_node(db.upcast());
583                     let hygiene = Hygiene::new(db.upcast(), ast.file_id);
584                     let mut cur = 0;
585                     let mut tree = None;
586                     ModPath::expand_use_item(
587                         InFile::new(ast.file_id, use_item),
588                         &hygiene,
589                         |_mod_path, use_tree, _is_glob, _alias| {
590                             if cur == *index {
591                                 tree = Some(use_tree.clone());
592                             }
593
594                             cur += 1;
595                         },
596                     );
597
598                     if let Some(tree) = tree {
599                         sink.push(UnresolvedImport { file: ast.file_id, node: AstPtr::new(&tree) });
600                     }
601                 }
602
603                 DiagnosticKind::UnconfiguredCode { ast, cfg, opts } => {
604                     let item = ast.to_node(db.upcast());
605                     sink.push(InactiveCode {
606                         file: ast.file_id,
607                         node: AstPtr::new(&item).into(),
608                         cfg: cfg.clone(),
609                         opts: opts.clone(),
610                     });
611                 }
612
613                 DiagnosticKind::UnresolvedProcMacro { ast } => {
614                     let mut precise_location = None;
615                     let (file, ast, name) = match ast {
616                         MacroCallKind::FnLike { ast_id } => {
617                             let node = ast_id.to_node(db.upcast());
618                             (ast_id.file_id, SyntaxNodePtr::from(AstPtr::new(&node)), None)
619                         }
620                         MacroCallKind::Derive { ast_id, derive_name, .. } => {
621                             let node = ast_id.to_node(db.upcast());
622
623                             // Compute the precise location of the macro name's token in the derive
624                             // list.
625                             // FIXME: This does not handle paths to the macro, but neither does the
626                             // rest of r-a.
627                             let derive_attrs =
628                                 node.attrs().filter_map(|attr| match attr.as_simple_call() {
629                                     Some((name, args)) if name == "derive" => Some(args),
630                                     _ => None,
631                                 });
632                             'outer: for attr in derive_attrs {
633                                 let tokens =
634                                     attr.syntax().children_with_tokens().filter_map(|elem| {
635                                         match elem {
636                                             syntax::NodeOrToken::Node(_) => None,
637                                             syntax::NodeOrToken::Token(tok) => Some(tok),
638                                         }
639                                     });
640                                 for token in tokens {
641                                     if token.kind() == SyntaxKind::IDENT
642                                         && token.text() == derive_name.as_str()
643                                     {
644                                         precise_location = Some(token.text_range());
645                                         break 'outer;
646                                     }
647                                 }
648                             }
649
650                             (
651                                 ast_id.file_id,
652                                 SyntaxNodePtr::from(AstPtr::new(&node)),
653                                 Some(derive_name.clone()),
654                             )
655                         }
656                     };
657                     sink.push(UnresolvedProcMacro {
658                         file,
659                         node: ast,
660                         precise_location,
661                         macro_name: name,
662                     });
663                 }
664
665                 DiagnosticKind::UnresolvedMacroCall { ast } => {
666                     let node = ast.to_node(db.upcast());
667                     sink.push(UnresolvedMacroCall { file: ast.file_id, node: AstPtr::new(&node) });
668                 }
669
670                 DiagnosticKind::MacroError { ast, message } => {
671                     let (file, ast) = match ast {
672                         MacroCallKind::FnLike { ast_id, .. } => {
673                             let node = ast_id.to_node(db.upcast());
674                             (ast_id.file_id, SyntaxNodePtr::from(AstPtr::new(&node)))
675                         }
676                         MacroCallKind::Derive { ast_id, .. } => {
677                             let node = ast_id.to_node(db.upcast());
678                             (ast_id.file_id, SyntaxNodePtr::from(AstPtr::new(&node)))
679                         }
680                     };
681                     sink.push(MacroError { file, node: ast, message: message.clone() });
682                 }
683             }
684         }
685     }
686 }