crates/ra_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(crate) mod raw;
  51 mod collector;
  52 mod mod_resolution;
  53 mod path_resolution;
  54
  55 #[cfg(test)]
  56 mod tests;
  57
  58 use std::sync::Arc;
  59
  60 use hir_expand::{
  61     ast_id_map::FileAstId, diagnostics::DiagnosticSink, name::Name, InFile, MacroDefId,
  62 };
  63 use once_cell::sync::Lazy;
  64 use ra_arena::Arena;
  65 use ra_db::{CrateId, Edition, FileId, FilePosition};
  66 use ra_prof::profile;
  67 use ra_syntax::{
  68     ast::{self, AstNode},
  69     SyntaxNode,
  70 };
  71 use rustc_hash::FxHashMap;
  72
  73 use crate::{
  74     builtin_type::BuiltinType,
  75     db::DefDatabase,
  76     nameres::{diagnostics::DefDiagnostic, path_resolution::ResolveMode},
  77     path::Path,
  78     per_ns::PerNs,
  79     AstId, FunctionId, ImplId, LocalImportId, LocalModuleId, ModuleDefId, ModuleId, TraitId,
  80 };
  81
  82 /// Contains all top-level defs from a macro-expanded crate
  83 #[derive(Debug, PartialEq, Eq)]
  84 pub struct CrateDefMap {
  85     pub root: LocalModuleId,
  86     pub modules: Arena<LocalModuleId, ModuleData>,
  87     pub(crate) krate: CrateId,
  88     /// The prelude module for this crate. This either comes from an import
  89     /// marked with the `prelude_import` attribute, or (in the normal case) from
  90     /// a dependency (`std` or `core`).
  91     pub(crate) prelude: Option<ModuleId>,
  92     pub(crate) extern_prelude: FxHashMap<Name, ModuleDefId>,
  93
  94     edition: Edition,
  95     diagnostics: Vec<DefDiagnostic>,
  96 }
  97
  98 impl std::ops::Index<LocalModuleId> for CrateDefMap {
  99     type Output = ModuleData;
 100     fn index(&self, id: LocalModuleId) -> &ModuleData {
 101         &self.modules[id]
 102     }
 103 }
 104
 105 #[derive(Debug, PartialEq, Eq, Clone, Copy, Hash)]
 106 pub enum ModuleOrigin {
 107     /// It should not be `None` after collecting definitions.
 108     Root(Option<FileId>),
 109     /// Note that non-inline modules, by definition, live inside non-macro file.
 110     File {
 111         declaration: AstId<ast::Module>,
 112         definition: FileId,
 113     },
 114     Inline {
 115         definition: AstId<ast::Module>,
 116     },
 117 }
 118
 119 impl Default for ModuleOrigin {
 120     fn default() -> Self {
 121         ModuleOrigin::Root(None)
 122     }
 123 }
 124
 125 impl ModuleOrigin {
 126     fn root(file_id: FileId) -> Self {
 127         ModuleOrigin::Root(Some(file_id))
 128     }
 129
 130     pub(crate) fn not_sure_file(file: Option<FileId>, declaration: AstId<ast::Module>) -> Self {
 131         match file {
 132             None => ModuleOrigin::Inline { definition: declaration },
 133             Some(definition) => ModuleOrigin::File { declaration, definition },
 134         }
 135     }
 136
 137     fn declaration(&self) -> Option<AstId<ast::Module>> {
 138         match self {
 139             ModuleOrigin::File { declaration: module, .. }
 140             | ModuleOrigin::Inline { definition: module, .. } => Some(*module),
 141             ModuleOrigin::Root(_) => None,
 142         }
 143     }
 144
 145     pub(crate) fn file_id(&self) -> Option<FileId> {
 146         match self {
 147             ModuleOrigin::File { definition: file_id, .. } | ModuleOrigin::Root(Some(file_id)) => {
 148                 Some(*file_id)
 149             }
 150             _ => None,
 151         }
 152     }
 153
 154     /// Returns a node which defines this module.
 155     /// That is, a file or a `mod foo {}` with items.
 156     fn definition_source(&self, db: &impl DefDatabase) -> InFile<ModuleSource> {
 157         match self {
 158             ModuleOrigin::File { definition: file_id, .. } | ModuleOrigin::Root(Some(file_id)) => {
 159                 let file_id = *file_id;
 160                 let sf = db.parse(file_id).tree();
 161                 return InFile::new(file_id.into(), ModuleSource::SourceFile(sf));
 162             }
 163             ModuleOrigin::Root(None) => unreachable!(),
 164             ModuleOrigin::Inline { definition } => {
 165                 InFile::new(definition.file_id, ModuleSource::Module(definition.to_node(db)))
 166             }
 167         }
 168     }
 169 }
 170
 171 #[derive(Default, Debug, PartialEq, Eq)]
 172 pub struct ModuleData {
 173     pub parent: Option<LocalModuleId>,
 174     pub children: FxHashMap<Name, LocalModuleId>,
 175     pub scope: ModuleScope,
 176
 177     /// Where does this module come from?
 178     pub origin: ModuleOrigin,
 179
 180     pub impls: Vec<ImplId>,
 181 }
 182
 183 #[derive(Default, Debug, PartialEq, Eq)]
 184 pub(crate) struct Declarations {
 185     fns: FxHashMap<FileAstId<ast::FnDef>, FunctionId>,
 186 }
 187
 188 #[derive(Debug, Default, PartialEq, Eq)]
 189 pub struct ModuleScope {
 190     items: FxHashMap<Name, Resolution>,
 191     /// Macros visable in current module in legacy textual scope
 192     ///
 193     /// For macros invoked by an unquatified identifier like `bar!()`, `legacy_macros` will be searched in first.
 194     /// If it yields no result, then it turns to module scoped `macros`.
 195     /// It macros with name quatified with a path like `crate::foo::bar!()`, `legacy_macros` will be skipped,
 196     /// and only normal scoped `macros` will be searched in.
 197     ///
 198     /// Note that this automatically inherit macros defined textually before the definition of module itself.
 199     ///
 200     /// Module scoped macros will be inserted into `items` instead of here.
 201     // FIXME: Macro shadowing in one module is not properly handled. Non-item place macros will
 202     // be all resolved to the last one defined if shadowing happens.
 203     legacy_macros: FxHashMap<Name, MacroDefId>,
 204 }
 205
 206 static BUILTIN_SCOPE: Lazy<FxHashMap<Name, Resolution>> = Lazy::new(|| {
 207     BuiltinType::ALL
 208         .iter()
 209         .map(|(name, ty)| {
 210             (name.clone(), Resolution { def: PerNs::types(ty.clone().into()), import: None })
 211         })
 212         .collect()
 213 });
 214
 215 /// Shadow mode for builtin type which can be shadowed by module.
 216 #[derive(Debug, Copy, Clone, PartialEq, Eq)]
 217 pub enum BuiltinShadowMode {
 218     // Prefer Module
 219     Module,
 220     // Prefer Other Types
 221     Other,
 222 }
 223
 224 /// Legacy macros can only be accessed through special methods like `get_legacy_macros`.
 225 /// Other methods will only resolve values, types and module scoped macros only.
 226 impl ModuleScope {
 227     pub fn entries<'a>(&'a self) -> impl Iterator<Item = (&'a Name, &'a Resolution)> + 'a {
 228         //FIXME: shadowing
 229         self.items.iter().chain(BUILTIN_SCOPE.iter())
 230     }
 231
 232     pub fn declarations(&self) -> impl Iterator<Item = ModuleDefId> + '_ {
 233         self.entries()
 234             .filter_map(|(_name, res)| if res.import.is_none() { Some(res.def) } else { None })
 235             .flat_map(|per_ns| {
 236                 per_ns.take_types().into_iter().chain(per_ns.take_values().into_iter())
 237             })
 238     }
 239
 240     /// Iterate over all module scoped macros
 241     pub fn macros<'a>(&'a self) -> impl Iterator<Item = (&'a Name, MacroDefId)> + 'a {
 242         self.items
 243             .iter()
 244             .filter_map(|(name, res)| res.def.take_macros().map(|macro_| (name, macro_)))
 245     }
 246
 247     /// Iterate over all legacy textual scoped macros visable at the end of the module
 248     pub fn legacy_macros<'a>(&'a self) -> impl Iterator<Item = (&'a Name, MacroDefId)> + 'a {
 249         self.legacy_macros.iter().map(|(name, def)| (name, *def))
 250     }
 251
 252     /// Get a name from current module scope, legacy macros are not included
 253     pub fn get(&self, name: &Name, shadow: BuiltinShadowMode) -> Option<&Resolution> {
 254         match shadow {
 255             BuiltinShadowMode::Module => self.items.get(name).or_else(|| BUILTIN_SCOPE.get(name)),
 256             BuiltinShadowMode::Other => {
 257                 let item = self.items.get(name);
 258                 if let Some(res) = item {
 259                     if let Some(ModuleDefId::ModuleId(_)) = res.def.take_types() {
 260                         return BUILTIN_SCOPE.get(name).or(item);
 261                     }
 262                 }
 263
 264                 item.or_else(|| BUILTIN_SCOPE.get(name))
 265             }
 266         }
 267     }
 268
 269     pub fn traits<'a>(&'a self) -> impl Iterator<Item = TraitId> + 'a {
 270         self.items.values().filter_map(|r| match r.def.take_types() {
 271             Some(ModuleDefId::TraitId(t)) => Some(t),
 272             _ => None,
 273         })
 274     }
 275
 276     fn get_legacy_macro(&self, name: &Name) -> Option<MacroDefId> {
 277         self.legacy_macros.get(name).copied()
 278     }
 279 }
 280
 281 #[derive(Debug, Clone, PartialEq, Eq, Default)]
 282 pub struct Resolution {
 283     /// None for unresolved
 284     pub def: PerNs,
 285     /// ident by which this is imported into local scope.
 286     pub import: Option<LocalImportId>,
 287 }
 288
 289 impl CrateDefMap {
 290     pub(crate) fn crate_def_map_query(
 291         // Note that this doesn't have `+ AstDatabase`!
 292         // This gurantess that `CrateDefMap` is stable across reparses.
 293         db: &impl DefDatabase,
 294         krate: CrateId,
 295     ) -> Arc<CrateDefMap> {
 296         let _p = profile("crate_def_map_query");
 297         let def_map = {
 298             let crate_graph = db.crate_graph();
 299             let edition = crate_graph.edition(krate);
 300             let mut modules: Arena<LocalModuleId, ModuleData> = Arena::default();
 301             let root = modules.alloc(ModuleData::default());
 302             CrateDefMap {
 303                 krate,
 304                 edition,
 305                 extern_prelude: FxHashMap::default(),
 306                 prelude: None,
 307                 root,
 308                 modules,
 309                 diagnostics: Vec::new(),
 310             }
 311         };
 312         let def_map = collector::collect_defs(db, def_map);
 313         Arc::new(def_map)
 314     }
 315
 316     pub fn add_diagnostics(
 317         &self,
 318         db: &impl DefDatabase,
 319         module: LocalModuleId,
 320         sink: &mut DiagnosticSink,
 321     ) {
 322         self.diagnostics.iter().for_each(|it| it.add_to(db, module, sink))
 323     }
 324
 325     pub fn modules_for_file(&self, file_id: FileId) -> impl Iterator<Item = LocalModuleId> + '_ {
 326         self.modules
 327             .iter()
 328             .filter(move |(_id, data)| data.origin.file_id() == Some(file_id))
 329             .map(|(id, _data)| id)
 330     }
 331
 332     pub(crate) fn resolve_path(
 333         &self,
 334         db: &impl DefDatabase,
 335         original_module: LocalModuleId,
 336         path: &Path,
 337         shadow: BuiltinShadowMode,
 338     ) -> (PerNs, Option<usize>) {
 339         let res =
 340             self.resolve_path_fp_with_macro(db, ResolveMode::Other, original_module, path, shadow);
 341         (res.resolved_def, res.segment_index)
 342     }
 343 }
 344
 345 impl ModuleData {
 346     /// Returns a node which defines this module. That is, a file or a `mod foo {}` with items.
 347     pub fn definition_source(&self, db: &impl DefDatabase) -> InFile<ModuleSource> {
 348         self.origin.definition_source(db)
 349     }
 350
 351     /// Returns a node which declares this module, either a `mod foo;` or a `mod foo {}`.
 352     /// `None` for the crate root or block.
 353     pub fn declaration_source(&self, db: &impl DefDatabase) -> Option<InFile<ast::Module>> {
 354         let decl = self.origin.declaration()?;
 355         let value = decl.to_node(db);
 356         Some(InFile { file_id: decl.file_id, value })
 357     }
 358 }
 359
 360 #[derive(Debug, Clone, PartialEq, Eq)]
 361 pub enum ModuleSource {
 362     SourceFile(ast::SourceFile),
 363     Module(ast::Module),
 364 }
 365
 366 impl ModuleSource {
 367     // FIXME: this methods do not belong here
 368     pub fn from_position(db: &impl DefDatabase, position: FilePosition) -> ModuleSource {
 369         let parse = db.parse(position.file_id);
 370         match &ra_syntax::algo::find_node_at_offset::<ast::Module>(
 371             parse.tree().syntax(),
 372             position.offset,
 373         ) {
 374             Some(m) if !m.has_semi() => ModuleSource::Module(m.clone()),
 375             _ => {
 376                 let source_file = parse.tree();
 377                 ModuleSource::SourceFile(source_file)
 378             }
 379         }
 380     }
 381
 382     pub fn from_child_node(db: &impl DefDatabase, child: InFile<&SyntaxNode>) -> ModuleSource {
 383         if let Some(m) =
 384             child.value.ancestors().filter_map(ast::Module::cast).find(|it| !it.has_semi())
 385         {
 386             ModuleSource::Module(m)
 387         } else {
 388             let file_id = child.file_id.original_file(db);
 389             let source_file = db.parse(file_id).tree();
 390             ModuleSource::SourceFile(source_file)
 391         }
 392     }
 393 }
 394
 395 mod diagnostics {
 396     use hir_expand::diagnostics::DiagnosticSink;
 397     use ra_db::RelativePathBuf;
 398     use ra_syntax::{ast, AstPtr};
 399
 400     use crate::{db::DefDatabase, diagnostics::UnresolvedModule, nameres::LocalModuleId, AstId};
 401
 402     #[derive(Debug, PartialEq, Eq)]
 403     pub(super) enum DefDiagnostic {
 404         UnresolvedModule {
 405             module: LocalModuleId,
 406             declaration: AstId<ast::Module>,
 407             candidate: RelativePathBuf,
 408         },
 409     }
 410
 411     impl DefDiagnostic {
 412         pub(super) fn add_to(
 413             &self,
 414             db: &impl DefDatabase,
 415             target_module: LocalModuleId,
 416             sink: &mut DiagnosticSink,
 417         ) {
 418             match self {
 419                 DefDiagnostic::UnresolvedModule { module, declaration, candidate } => {
 420                     if *module != target_module {
 421                         return;
 422                     }
 423                     let decl = declaration.to_node(db);
 424                     sink.push(UnresolvedModule {
 425                         file: declaration.file_id,
 426                         decl: AstPtr::new(&decl),
 427                         candidate: candidate.clone(),
 428                     })
 429                 }
 430             }
 431         }
 432     }
 433 }