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