crates/hir_def/src/nameres.rs

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