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