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 pub mod diagnostics;
  51 mod collector;
  52 mod mod_resolution;
  53 mod path_resolution;
  54 mod proc_macro;
  55
  56 #[cfg(test)]
  57 mod tests;
  58
  59 use std::sync::Arc;
  60
  61 use base_db::{CrateId, Edition, FileId};
  62 use hir_expand::{name::Name, InFile, MacroDefId};
  63 use la_arena::Arena;
  64 use profile::Count;
  65 use rustc_hash::FxHashMap;
  66 use stdx::format_to;
  67 use syntax::ast;
  68
  69 use crate::{
  70     db::DefDatabase,
  71     item_scope::{BuiltinShadowMode, ItemScope},
  72     nameres::{diagnostics::DefDiagnostic, path_resolution::ResolveMode},
  73     path::ModPath,
  74     per_ns::PerNs,
  75     AstId, BlockId, BlockLoc, LocalModuleId, ModuleDefId, ModuleId,
  76 };
  77
  78 use self::proc_macro::ProcMacroDef;
  79
  80 /// Contains the results of (early) name resolution.
  81 ///
  82 /// A `DefMap` stores the module tree and the definitions that are in scope in every module after
  83 /// item-level macros have been expanded.
  84 ///
  85 /// Every crate has a primary `DefMap` whose root is the crate's main file (`main.rs`/`lib.rs`),
  86 /// computed by the `crate_def_map` query. Additionally, every block expression introduces the
  87 /// opportunity to write arbitrary item and module hierarchies, and thus gets its own `DefMap` that
  88 /// is computed by the `block_def_map` query.
  89 #[derive(Debug, PartialEq, Eq)]
  90 pub struct DefMap {
  91     _c: Count<Self>,
  92     block: Option<BlockInfo>,
  93     root: LocalModuleId,
  94     modules: Arena<ModuleData>,
  95     krate: CrateId,
  96     /// The prelude module for this crate. This either comes from an import
  97     /// marked with the `prelude_import` attribute, or (in the normal case) from
  98     /// a dependency (`std` or `core`).
  99     prelude: Option<ModuleId>,
 100     extern_prelude: FxHashMap<Name, ModuleDefId>,
 101
 102     /// Side table with additional proc. macro info, for use by name resolution in downstream
 103     /// crates.
 104     ///
 105     /// (the primary purpose is to resolve derive helpers)
 106     exported_proc_macros: FxHashMap<MacroDefId, ProcMacroDef>,
 107
 108     edition: Edition,
 109     diagnostics: Vec<DefDiagnostic>,
 110 }
 111
 112 /// For `DefMap`s computed for a block expression, this stores its location in the parent map.
 113 #[derive(Debug, PartialEq, Eq, Clone, Copy)]
 114 struct BlockInfo {
 115     /// The `BlockId` this `DefMap` was created from.
 116     block: BlockId,
 117     /// The containing module.
 118     parent: ModuleId,
 119 }
 120
 121 impl std::ops::Index<LocalModuleId> for DefMap {
 122     type Output = ModuleData;
 123     fn index(&self, id: LocalModuleId) -> &ModuleData {
 124         &self.modules[id]
 125     }
 126 }
 127
 128 #[derive(Debug, PartialEq, Eq, Clone, Copy, Hash)]
 129 pub enum ModuleOrigin {
 130     CrateRoot {
 131         definition: FileId,
 132     },
 133     /// Note that non-inline modules, by definition, live inside non-macro file.
 134     File {
 135         is_mod_rs: bool,
 136         declaration: AstId<ast::Module>,
 137         definition: FileId,
 138     },
 139     Inline {
 140         definition: AstId<ast::Module>,
 141     },
 142     /// Pseudo-module introduced by a block scope (contains only inner items).
 143     BlockExpr {
 144         block: AstId<ast::BlockExpr>,
 145     },
 146 }
 147
 148 impl ModuleOrigin {
 149     fn declaration(&self) -> Option<AstId<ast::Module>> {
 150         match self {
 151             ModuleOrigin::File { declaration: module, .. }
 152             | ModuleOrigin::Inline { definition: module, .. } => Some(*module),
 153             ModuleOrigin::CrateRoot { .. } | ModuleOrigin::BlockExpr { .. } => None,
 154         }
 155     }
 156
 157     pub fn file_id(&self) -> Option<FileId> {
 158         match self {
 159             ModuleOrigin::File { definition, .. } | ModuleOrigin::CrateRoot { definition } => {
 160                 Some(*definition)
 161             }
 162             _ => None,
 163         }
 164     }
 165
 166     pub fn is_inline(&self) -> bool {
 167         match self {
 168             ModuleOrigin::Inline { .. } | ModuleOrigin::BlockExpr { .. } => true,
 169             ModuleOrigin::CrateRoot { .. } | ModuleOrigin::File { .. } => false,
 170         }
 171     }
 172
 173     /// Returns a node which defines this module.
 174     /// That is, a file or a `mod foo {}` with items.
 175     fn definition_source(&self, db: &dyn DefDatabase) -> InFile<ModuleSource> {
 176         match self {
 177             ModuleOrigin::File { definition, .. } | ModuleOrigin::CrateRoot { definition } => {
 178                 let file_id = *definition;
 179                 let sf = db.parse(file_id).tree();
 180                 InFile::new(file_id.into(), ModuleSource::SourceFile(sf))
 181             }
 182             ModuleOrigin::Inline { definition } => InFile::new(
 183                 definition.file_id,
 184                 ModuleSource::Module(definition.to_node(db.upcast())),
 185             ),
 186             ModuleOrigin::BlockExpr { block } => {
 187                 InFile::new(block.file_id, ModuleSource::BlockExpr(block.to_node(db.upcast())))
 188             }
 189         }
 190     }
 191 }
 192
 193 #[derive(Debug, PartialEq, Eq)]
 194 pub struct ModuleData {
 195     pub parent: Option<LocalModuleId>,
 196     pub children: FxHashMap<Name, LocalModuleId>,
 197     pub scope: ItemScope,
 198
 199     /// Where does this module come from?
 200     pub origin: ModuleOrigin,
 201 }
 202
 203 impl DefMap {
 204     pub(crate) fn crate_def_map_query(db: &dyn DefDatabase, krate: CrateId) -> Arc<DefMap> {
 205         let _p = profile::span("crate_def_map_query").detail(|| {
 206             db.crate_graph()[krate].display_name.as_deref().unwrap_or_default().to_string()
 207         });
 208
 209         let crate_graph = db.crate_graph();
 210
 211         let edition = crate_graph[krate].edition;
 212         let origin = ModuleOrigin::CrateRoot { definition: crate_graph[krate].root_file_id };
 213         let def_map = DefMap::empty(krate, edition, origin);
 214         let def_map = collector::collect_defs(db, def_map, None);
 215
 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(
 234             block.module.krate,
 235             parent_map.edition,
 236             ModuleOrigin::BlockExpr { block: block.ast_id },
 237         );
 238         def_map.block = Some(block_info);
 239
 240         let def_map = collector::collect_defs(db, def_map, Some(block.ast_id));
 241         Some(Arc::new(def_map))
 242     }
 243
 244     fn empty(krate: CrateId, edition: Edition, root_module_origin: ModuleOrigin) -> DefMap {
 245         let mut modules: Arena<ModuleData> = Arena::default();
 246         let root = modules.alloc(ModuleData::new(root_module_origin));
 247         DefMap {
 248             _c: Count::new(),
 249             block: None,
 250             krate,
 251             edition,
 252             extern_prelude: FxHashMap::default(),
 253             exported_proc_macros: FxHashMap::default(),
 254             prelude: None,
 255             root,
 256             modules,
 257             diagnostics: Vec::new(),
 258         }
 259     }
 260
 261     pub fn modules_for_file(&self, file_id: FileId) -> impl Iterator<Item = LocalModuleId> + '_ {
 262         self.modules
 263             .iter()
 264             .filter(move |(_id, data)| data.origin.file_id() == Some(file_id))
 265             .map(|(id, _data)| id)
 266     }
 267
 268     pub fn modules(&self) -> impl Iterator<Item = (LocalModuleId, &ModuleData)> + '_ {
 269         self.modules.iter()
 270     }
 271
 272     pub fn root(&self) -> LocalModuleId {
 273         self.root
 274     }
 275
 276     pub(crate) fn krate(&self) -> CrateId {
 277         self.krate
 278     }
 279
 280     pub(crate) fn block_id(&self) -> Option<BlockId> {
 281         self.block.as_ref().map(|block| block.block)
 282     }
 283
 284     pub(crate) fn prelude(&self) -> Option<ModuleId> {
 285         self.prelude
 286     }
 287
 288     pub(crate) fn extern_prelude(&self) -> impl Iterator<Item = (&Name, &ModuleDefId)> + '_ {
 289         self.extern_prelude.iter()
 290     }
 291
 292     pub fn module_id(&self, local_id: LocalModuleId) -> ModuleId {
 293         let block = self.block.as_ref().map(|b| b.block);
 294         ModuleId { krate: self.krate, local_id, block }
 295     }
 296
 297     pub(crate) fn crate_root(&self, db: &dyn DefDatabase) -> ModuleId {
 298         self.with_ancestor_maps(db, self.root, &mut |def_map, _module| {
 299             if def_map.block.is_none() {
 300                 Some(def_map.module_id(def_map.root))
 301             } else {
 302                 None
 303             }
 304         })
 305         .expect("DefMap chain without root")
 306     }
 307
 308     pub(crate) fn resolve_path(
 309         &self,
 310         db: &dyn DefDatabase,
 311         original_module: LocalModuleId,
 312         path: &ModPath,
 313         shadow: BuiltinShadowMode,
 314     ) -> (PerNs, Option<usize>) {
 315         let res =
 316             self.resolve_path_fp_with_macro(db, ResolveMode::Other, original_module, path, shadow);
 317         (res.resolved_def, res.segment_index)
 318     }
 319
 320     pub(crate) fn resolve_path_locally(
 321         &self,
 322         db: &dyn DefDatabase,
 323         original_module: LocalModuleId,
 324         path: &ModPath,
 325         shadow: BuiltinShadowMode,
 326     ) -> (PerNs, Option<usize>) {
 327         let res = self.resolve_path_fp_with_macro_single(
 328             db,
 329             ResolveMode::Other,
 330             original_module,
 331             path,
 332             shadow,
 333         );
 334         (res.resolved_def, res.segment_index)
 335     }
 336
 337     /// Ascends the `DefMap` hierarchy and calls `f` with every `DefMap` and containing module.
 338     ///
 339     /// If `f` returns `Some(val)`, iteration is stopped and `Some(val)` is returned. If `f` returns
 340     /// `None`, iteration continues.
 341     pub fn with_ancestor_maps<T>(
 342         &self,
 343         db: &dyn DefDatabase,
 344         local_mod: LocalModuleId,
 345         f: &mut dyn FnMut(&DefMap, LocalModuleId) -> Option<T>,
 346     ) -> Option<T> {
 347         if let Some(it) = f(self, local_mod) {
 348             return Some(it);
 349         }
 350         let mut block = self.block;
 351         while let Some(block_info) = block {
 352             let parent = block_info.parent.def_map(db);
 353             if let Some(it) = f(&parent, block_info.parent.local_id) {
 354                 return Some(it);
 355             }
 356             block = parent.block;
 357         }
 358
 359         None
 360     }
 361
 362     /// If this `DefMap` is for a block expression, returns the module containing the block (which
 363     /// might again be a block, or a module inside a block).
 364     pub fn parent(&self) -> Option<ModuleId> {
 365         Some(self.block?.parent)
 366     }
 367
 368     /// Returns the module containing `local_mod`, either the parent `mod`, or the module containing
 369     /// the block, if `self` corresponds to a block expression.
 370     pub fn containing_module(&self, local_mod: LocalModuleId) -> Option<ModuleId> {
 371         match &self[local_mod].parent {
 372             Some(parent) => Some(self.module_id(*parent)),
 373             None => self.block.as_ref().map(|block| block.parent),
 374         }
 375     }
 376
 377     // FIXME: this can use some more human-readable format (ideally, an IR
 378     // even), as this should be a great debugging aid.
 379     pub fn dump(&self, db: &dyn DefDatabase) -> String {
 380         let mut buf = String::new();
 381         let mut arc;
 382         let mut current_map = self;
 383         while let Some(block) = &current_map.block {
 384             go(&mut buf, current_map, "block scope", current_map.root);
 385             buf.push('\n');
 386             arc = block.parent.def_map(db);
 387             current_map = &*arc;
 388         }
 389         go(&mut buf, current_map, "crate", current_map.root);
 390         return buf;
 391
 392         fn go(buf: &mut String, map: &DefMap, path: &str, module: LocalModuleId) {
 393             format_to!(buf, "{}\n", path);
 394
 395             map.modules[module].scope.dump(buf);
 396
 397             for (name, child) in map.modules[module].children.iter() {
 398                 let path = format!("{}::{}", path, name);
 399                 buf.push('\n');
 400                 go(buf, map, &path, *child);
 401             }
 402         }
 403     }
 404
 405     pub fn dump_block_scopes(&self, db: &dyn DefDatabase) -> String {
 406         let mut buf = String::new();
 407         let mut arc;
 408         let mut current_map = self;
 409         while let Some(block) = &current_map.block {
 410             format_to!(buf, "{:?} in {:?}\n", block.block, block.parent);
 411             arc = block.parent.def_map(db);
 412             current_map = &*arc;
 413         }
 414
 415         format_to!(buf, "crate scope\n");
 416         buf
 417     }
 418
 419     fn shrink_to_fit(&mut self) {
 420         // Exhaustive match to require handling new fields.
 421         let Self {
 422             _c: _,
 423             exported_proc_macros,
 424             extern_prelude,
 425             diagnostics,
 426             modules,
 427             block: _,
 428             edition: _,
 429             krate: _,
 430             prelude: _,
 431             root: _,
 432         } = self;
 433
 434         extern_prelude.shrink_to_fit();
 435         exported_proc_macros.shrink_to_fit();
 436         diagnostics.shrink_to_fit();
 437         modules.shrink_to_fit();
 438         for (_, module) in modules.iter_mut() {
 439             module.children.shrink_to_fit();
 440             module.scope.shrink_to_fit();
 441         }
 442     }
 443
 444     /// Get a reference to the def map's diagnostics.
 445     pub fn diagnostics(&self) -> &[DefDiagnostic] {
 446         self.diagnostics.as_slice()
 447     }
 448 }
 449
 450 impl ModuleData {
 451     pub(crate) fn new(origin: ModuleOrigin) -> Self {
 452         ModuleData {
 453             parent: None,
 454             children: FxHashMap::default(),
 455             scope: ItemScope::default(),
 456             origin,
 457         }
 458     }
 459
 460     /// Returns a node which defines this module. That is, a file or a `mod foo {}` with items.
 461     pub fn definition_source(&self, db: &dyn DefDatabase) -> InFile<ModuleSource> {
 462         self.origin.definition_source(db)
 463     }
 464
 465     /// Returns a node which declares this module, either a `mod foo;` or a `mod foo {}`.
 466     /// `None` for the crate root or block.
 467     pub fn declaration_source(&self, db: &dyn DefDatabase) -> Option<InFile<ast::Module>> {
 468         let decl = self.origin.declaration()?;
 469         let value = decl.to_node(db.upcast());
 470         Some(InFile { file_id: decl.file_id, value })
 471     }
 472 }
 473
 474 #[derive(Debug, Clone, PartialEq, Eq)]
 475 pub enum ModuleSource {
 476     SourceFile(ast::SourceFile),
 477     Module(ast::Module),
 478     BlockExpr(ast::BlockExpr),
 479 }