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
  57 use std::sync::Arc;
  58
  59 use arena::Arena;
  60 use base_db::{CrateId, Edition, FileId};
  61 use hir_expand::{diagnostics::DiagnosticSink, name::Name, InFile};
  62 use rustc_hash::FxHashMap;
  63 use stdx::format_to;
  64 use syntax::ast;
  65
  66 use crate::{
  67     db::DefDatabase,
  68     item_scope::{BuiltinShadowMode, ItemScope},
  69     nameres::{diagnostics::DefDiagnostic, path_resolution::ResolveMode},
  70     path::ModPath,
  71     per_ns::PerNs,
  72     AstId, LocalModuleId, ModuleDefId, ModuleId,
  73 };
  74
  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>,
  86
  87     edition: Edition,
  88     diagnostics: Vec<DefDiagnostic>,
  89 }
  90
  91 impl std::ops::Index<LocalModuleId> for CrateDefMap {
  92     type Output = ModuleData;
  93     fn index(&self, id: LocalModuleId) -> &ModuleData {
  94         &self.modules[id]
  95     }
  96 }
  97
  98 #[derive(Debug, PartialEq, Eq, Clone, Copy, Hash)]
  99 pub enum ModuleOrigin {
 100     CrateRoot {
 101         definition: FileId,
 102     },
 103     /// Note that non-inline modules, by definition, live inside non-macro file.
 104     File {
 105         is_mod_rs: bool,
 106         declaration: AstId<ast::Module>,
 107         definition: FileId,
 108     },
 109     Inline {
 110         definition: AstId<ast::Module>,
 111     },
 112 }
 113
 114 impl Default for ModuleOrigin {
 115     fn default() -> Self {
 116         ModuleOrigin::CrateRoot { definition: FileId(0) }
 117     }
 118 }
 119
 120 impl ModuleOrigin {
 121     fn declaration(&self) -> Option<AstId<ast::Module>> {
 122         match self {
 123             ModuleOrigin::File { declaration: module, .. }
 124             | ModuleOrigin::Inline { definition: module, .. } => Some(*module),
 125             ModuleOrigin::CrateRoot { .. } => None,
 126         }
 127     }
 128
 129     pub fn file_id(&self) -> Option<FileId> {
 130         match self {
 131             ModuleOrigin::File { definition, .. } | ModuleOrigin::CrateRoot { definition } => {
 132                 Some(*definition)
 133             }
 134             _ => None,
 135         }
 136     }
 137
 138     pub fn is_inline(&self) -> bool {
 139         match self {
 140             ModuleOrigin::Inline { .. } => true,
 141             ModuleOrigin::CrateRoot { .. } | ModuleOrigin::File { .. } => false,
 142         }
 143     }
 144
 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> {
 148         match self {
 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))
 153             }
 154             ModuleOrigin::Inline { definition } => InFile::new(
 155                 definition.file_id,
 156                 ModuleSource::Module(definition.to_node(db.upcast())),
 157             ),
 158         }
 159     }
 160 }
 161
 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,
 167
 168     /// Where does this module come from?
 169     pub origin: ModuleOrigin,
 170 }
 171
 172 impl CrateDefMap {
 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()
 176         });
 177         let def_map = {
 178             let edition = db.crate_graph()[krate].edition;
 179             let mut modules: Arena<ModuleData> = Arena::default();
 180             let root = modules.alloc(ModuleData::default());
 181             CrateDefMap {
 182                 krate,
 183                 edition,
 184                 extern_prelude: FxHashMap::default(),
 185                 prelude: None,
 186                 root,
 187                 modules,
 188                 diagnostics: Vec::new(),
 189             }
 190         };
 191         let def_map = collector::collect_defs(db, def_map);
 192         Arc::new(def_map)
 193     }
 194
 195     pub fn add_diagnostics(
 196         &self,
 197         db: &dyn DefDatabase,
 198         module: LocalModuleId,
 199         sink: &mut DiagnosticSink,
 200     ) {
 201         self.diagnostics.iter().for_each(|it| it.add_to(db, module, sink))
 202     }
 203
 204     pub fn modules_for_file(&self, file_id: FileId) -> impl Iterator<Item = LocalModuleId> + '_ {
 205         self.modules
 206             .iter()
 207             .filter(move |(_id, data)| data.origin.file_id() == Some(file_id))
 208             .map(|(id, _data)| id)
 209     }
 210
 211     pub(crate) fn resolve_path(
 212         &self,
 213         db: &dyn DefDatabase,
 214         original_module: LocalModuleId,
 215         path: &ModPath,
 216         shadow: BuiltinShadowMode,
 217     ) -> (PerNs, Option<usize>) {
 218         let res =
 219             self.resolve_path_fp_with_macro(db, ResolveMode::Other, original_module, path, shadow);
 220         (res.resolved_def, res.segment_index)
 221     }
 222
 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);
 228         return buf;
 229
 230         fn go(buf: &mut String, map: &CrateDefMap, path: &str, module: LocalModuleId) {
 231             format_to!(buf, "{}\n", path);
 232
 233             let mut entries: Vec<_> = map.modules[module].scope.resolutions().collect();
 234             entries.sort_by_key(|(name, _)| name.clone());
 235
 236             for (name, def) in entries {
 237                 format_to!(buf, "{}:", name.map_or("_".to_string(), |name| name.to_string()));
 238
 239                 if def.types.is_some() {
 240                     buf.push_str(" t");
 241                 }
 242                 if def.values.is_some() {
 243                     buf.push_str(" v");
 244                 }
 245                 if def.macros.is_some() {
 246                     buf.push_str(" m");
 247                 }
 248                 if def.is_none() {
 249                     buf.push_str(" _");
 250                 }
 251
 252                 buf.push_str("\n");
 253             }
 254
 255             for (name, child) in map.modules[module].children.iter() {
 256                 let path = format!("{}::{}", path, name);
 257                 buf.push('\n');
 258                 go(buf, map, &path, *child);
 259             }
 260         }
 261     }
 262 }
 263
 264 impl ModuleData {
 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)
 268     }
 269
 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 })
 276     }
 277 }
 278
 279 #[derive(Debug, Clone, PartialEq, Eq)]
 280 pub enum ModuleSource {
 281     SourceFile(ast::SourceFile),
 282     Module(ast::Module),
 283 }
 284
 285 mod diagnostics {
 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};
 291
 292     use crate::path::ModPath;
 293     use crate::{db::DefDatabase, diagnostics::*, nameres::LocalModuleId, AstId};
 294
 295     #[derive(Debug, PartialEq, Eq)]
 296     enum DiagnosticKind {
 297         UnresolvedModule { declaration: AstId<ast::Module>, candidate: String },
 298
 299         UnresolvedExternCrate { ast: AstId<ast::ExternCrate> },
 300
 301         UnresolvedImport { ast: AstId<ast::Use>, index: usize },
 302
 303         UnconfiguredCode { ast: AstId<ast::Item>, cfg: CfgExpr, opts: CfgOptions },
 304     }
 305
 306     #[derive(Debug, PartialEq, Eq)]
 307     pub(super) struct DefDiagnostic {
 308         in_module: LocalModuleId,
 309         kind: DiagnosticKind,
 310     }
 311
 312     impl DefDiagnostic {
 313         pub(super) fn unresolved_module(
 314             container: LocalModuleId,
 315             declaration: AstId<ast::Module>,
 316             candidate: String,
 317         ) -> Self {
 318             Self {
 319                 in_module: container,
 320                 kind: DiagnosticKind::UnresolvedModule { declaration, candidate },
 321             }
 322         }
 323
 324         pub(super) fn unresolved_extern_crate(
 325             container: LocalModuleId,
 326             declaration: AstId<ast::ExternCrate>,
 327         ) -> Self {
 328             Self {
 329                 in_module: container,
 330                 kind: DiagnosticKind::UnresolvedExternCrate { ast: declaration },
 331             }
 332         }
 333
 334         pub(super) fn unresolved_import(
 335             container: LocalModuleId,
 336             ast: AstId<ast::Use>,
 337             index: usize,
 338         ) -> Self {
 339             Self { in_module: container, kind: DiagnosticKind::UnresolvedImport { ast, index } }
 340         }
 341
 342         pub(super) fn unconfigured_code(
 343             container: LocalModuleId,
 344             ast: AstId<ast::Item>,
 345             cfg: CfgExpr,
 346             opts: CfgOptions,
 347         ) -> Self {
 348             Self { in_module: container, kind: DiagnosticKind::UnconfiguredCode { ast, cfg, opts } }
 349         }
 350
 351         pub(super) fn add_to(
 352             &self,
 353             db: &dyn DefDatabase,
 354             target_module: LocalModuleId,
 355             sink: &mut DiagnosticSink,
 356         ) {
 357             if self.in_module != target_module {
 358                 return;
 359             }
 360
 361             match &self.kind {
 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(),
 368                     })
 369                 }
 370
 371                 DiagnosticKind::UnresolvedExternCrate { ast } => {
 372                     let item = ast.to_node(db.upcast());
 373                     sink.push(UnresolvedExternCrate {
 374                         file: ast.file_id,
 375                         item: AstPtr::new(&item),
 376                     });
 377                 }
 378
 379                 DiagnosticKind::UnresolvedImport { ast, index } => {
 380                     let use_item = ast.to_node(db.upcast());
 381                     let hygiene = Hygiene::new(db.upcast(), ast.file_id);
 382                     let mut cur = 0;
 383                     let mut tree = None;
 384                     ModPath::expand_use_item(
 385                         InFile::new(ast.file_id, use_item),
 386                         &hygiene,
 387                         |_mod_path, use_tree, _is_glob, _alias| {
 388                             if cur == *index {
 389                                 tree = Some(use_tree.clone());
 390                             }
 391
 392                             cur += 1;
 393                         },
 394                     );
 395
 396                     if let Some(tree) = tree {
 397                         sink.push(UnresolvedImport { file: ast.file_id, node: AstPtr::new(&tree) });
 398                     }
 399                 }
 400
 401                 DiagnosticKind::UnconfiguredCode { ast, cfg, opts } => {
 402                     let item = ast.to_node(db.upcast());
 403                     sink.push(InactiveCode {
 404                         file: ast.file_id,
 405                         node: AstPtr::new(&item).into(),
 406                         cfg: cfg.clone(),
 407                         opts: opts.clone(),
 408                     });
 409                 }
 410             }
 411         }
 412     }
 413 }