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 either::Either;
  61 use hir_expand::{
  62     ast_id_map::FileAstId, diagnostics::DiagnosticSink, name::Name, InFile, MacroDefId,
  63 };
  64 use once_cell::sync::Lazy;
  65 use ra_arena::Arena;
  66 use ra_db::{CrateId, Edition, FileId};
  67 use ra_prof::profile;
  68 use ra_syntax::ast;
  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::Path,
  76     per_ns::PerNs,
  77     AstId, FunctionId, 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(Default, Debug, PartialEq, Eq)]
 104 pub struct ModuleData {
 105     pub parent: Option<LocalModuleId>,
 106     pub children: FxHashMap<Name, LocalModuleId>,
 107     pub scope: ModuleScope,
 108
 109     //  FIXME: these can't be both null, we need a three-state enum here.
 110     /// None for root
 111     pub declaration: Option<AstId<ast::Module>>,
 112     /// None for inline modules.
 113     ///
 114     /// Note that non-inline modules, by definition, live inside non-macro file.
 115     pub definition: Option<FileId>,
 116
 117     pub impls: Vec<ImplId>,
 118 }
 119
 120 #[derive(Default, Debug, PartialEq, Eq)]
 121 pub(crate) struct Declarations {
 122     fns: FxHashMap<FileAstId<ast::FnDef>, FunctionId>,
 123 }
 124
 125 #[derive(Debug, Default, PartialEq, Eq)]
 126 pub struct ModuleScope {
 127     items: FxHashMap<Name, Resolution>,
 128     /// Macros visable in current module in legacy textual scope
 129     ///
 130     /// For macros invoked by an unquatified identifier like `bar!()`, `legacy_macros` will be searched in first.
 131     /// If it yields no result, then it turns to module scoped `macros`.
 132     /// It macros with name quatified with a path like `crate::foo::bar!()`, `legacy_macros` will be skipped,
 133     /// and only normal scoped `macros` will be searched in.
 134     ///
 135     /// Note that this automatically inherit macros defined textually before the definition of module itself.
 136     ///
 137     /// Module scoped macros will be inserted into `items` instead of here.
 138     // FIXME: Macro shadowing in one module is not properly handled. Non-item place macros will
 139     // be all resolved to the last one defined if shadowing happens.
 140     legacy_macros: FxHashMap<Name, MacroDefId>,
 141 }
 142
 143 static BUILTIN_SCOPE: Lazy<FxHashMap<Name, Resolution>> = Lazy::new(|| {
 144     BuiltinType::ALL
 145         .iter()
 146         .map(|(name, ty)| {
 147             (name.clone(), Resolution { def: PerNs::types(ty.clone().into()), import: None })
 148         })
 149         .collect()
 150 });
 151
 152 /// Shadow mode for builtin type which can be shadowed by module.
 153 #[derive(Debug, Copy, Clone, PartialEq, Eq)]
 154 pub enum BuiltinShadowMode {
 155     // Prefer Module
 156     Module,
 157     // Prefer Other Types
 158     Other,
 159 }
 160
 161 /// Legacy macros can only be accessed through special methods like `get_legacy_macros`.
 162 /// Other methods will only resolve values, types and module scoped macros only.
 163 impl ModuleScope {
 164     pub fn entries<'a>(&'a self) -> impl Iterator<Item = (&'a Name, &'a Resolution)> + 'a {
 165         //FIXME: shadowing
 166         self.items.iter().chain(BUILTIN_SCOPE.iter())
 167     }
 168
 169     pub fn declarations(&self) -> impl Iterator<Item = ModuleDefId> + '_ {
 170         self.entries()
 171             .filter_map(|(_name, res)| if res.import.is_none() { Some(res.def) } else { None })
 172             .flat_map(|per_ns| {
 173                 per_ns.take_types().into_iter().chain(per_ns.take_values().into_iter())
 174             })
 175     }
 176
 177     /// Iterate over all module scoped macros
 178     pub fn macros<'a>(&'a self) -> impl Iterator<Item = (&'a Name, MacroDefId)> + 'a {
 179         self.items
 180             .iter()
 181             .filter_map(|(name, res)| res.def.take_macros().map(|macro_| (name, macro_)))
 182     }
 183
 184     /// Iterate over all legacy textual scoped macros visable at the end of the module
 185     pub fn legacy_macros<'a>(&'a self) -> impl Iterator<Item = (&'a Name, MacroDefId)> + 'a {
 186         self.legacy_macros.iter().map(|(name, def)| (name, *def))
 187     }
 188
 189     /// Get a name from current module scope, legacy macros are not included
 190     pub fn get(&self, name: &Name, shadow: BuiltinShadowMode) -> Option<&Resolution> {
 191         match shadow {
 192             BuiltinShadowMode::Module => self.items.get(name).or_else(|| BUILTIN_SCOPE.get(name)),
 193             BuiltinShadowMode::Other => {
 194                 let item = self.items.get(name);
 195                 if let Some(res) = item {
 196                     if let Some(ModuleDefId::ModuleId(_)) = res.def.take_types() {
 197                         return BUILTIN_SCOPE.get(name).or(item);
 198                     }
 199                 }
 200
 201                 item.or_else(|| BUILTIN_SCOPE.get(name))
 202             }
 203         }
 204     }
 205
 206     pub fn traits<'a>(&'a self) -> impl Iterator<Item = TraitId> + 'a {
 207         self.items.values().filter_map(|r| match r.def.take_types() {
 208             Some(ModuleDefId::TraitId(t)) => Some(t),
 209             _ => None,
 210         })
 211     }
 212
 213     fn get_legacy_macro(&self, name: &Name) -> Option<MacroDefId> {
 214         self.legacy_macros.get(name).copied()
 215     }
 216 }
 217
 218 #[derive(Debug, Clone, PartialEq, Eq, Default)]
 219 pub struct Resolution {
 220     /// None for unresolved
 221     pub def: PerNs,
 222     /// ident by which this is imported into local scope.
 223     pub import: Option<LocalImportId>,
 224 }
 225
 226 impl CrateDefMap {
 227     pub(crate) fn crate_def_map_query(
 228         // Note that this doesn't have `+ AstDatabase`!
 229         // This gurantess that `CrateDefMap` is stable across reparses.
 230         db: &impl DefDatabase,
 231         krate: CrateId,
 232     ) -> Arc<CrateDefMap> {
 233         let _p = profile("crate_def_map_query");
 234         let def_map = {
 235             let crate_graph = db.crate_graph();
 236             let edition = crate_graph.edition(krate);
 237             let mut modules: Arena<LocalModuleId, ModuleData> = Arena::default();
 238             let root = modules.alloc(ModuleData::default());
 239             CrateDefMap {
 240                 krate,
 241                 edition,
 242                 extern_prelude: FxHashMap::default(),
 243                 prelude: None,
 244                 root,
 245                 modules,
 246                 diagnostics: Vec::new(),
 247             }
 248         };
 249         let def_map = collector::collect_defs(db, def_map);
 250         Arc::new(def_map)
 251     }
 252
 253     pub fn add_diagnostics(
 254         &self,
 255         db: &impl DefDatabase,
 256         module: LocalModuleId,
 257         sink: &mut DiagnosticSink,
 258     ) {
 259         self.diagnostics.iter().for_each(|it| it.add_to(db, module, sink))
 260     }
 261
 262     pub fn modules_for_file(&self, file_id: FileId) -> impl Iterator<Item = LocalModuleId> + '_ {
 263         self.modules
 264             .iter()
 265             .filter(move |(_id, data)| data.definition == Some(file_id))
 266             .map(|(id, _data)| id)
 267     }
 268
 269     pub(crate) fn resolve_path(
 270         &self,
 271         db: &impl DefDatabase,
 272         original_module: LocalModuleId,
 273         path: &Path,
 274         shadow: BuiltinShadowMode,
 275     ) -> (PerNs, Option<usize>) {
 276         let res =
 277             self.resolve_path_fp_with_macro(db, ResolveMode::Other, original_module, path, shadow);
 278         (res.resolved_def, res.segment_index)
 279     }
 280 }
 281
 282 impl ModuleData {
 283     /// Returns a node which defines this module. That is, a file or a `mod foo {}` with items.
 284     pub fn definition_source(
 285         &self,
 286         db: &impl DefDatabase,
 287     ) -> InFile<Either<ast::SourceFile, ast::Module>> {
 288         if let Some(file_id) = self.definition {
 289             let sf = db.parse(file_id).tree();
 290             return InFile::new(file_id.into(), Either::Left(sf));
 291         }
 292         let decl = self.declaration.unwrap();
 293         InFile::new(decl.file_id, Either::Right(decl.to_node(db)))
 294     }
 295
 296     /// Returns a node which declares this module, either a `mod foo;` or a `mod foo {}`.
 297     /// `None` for the crate root.
 298     pub fn declaration_source(&self, db: &impl DefDatabase) -> Option<InFile<ast::Module>> {
 299         let decl = self.declaration?;
 300         let value = decl.to_node(db);
 301         Some(InFile { file_id: decl.file_id, value })
 302     }
 303 }
 304
 305 mod diagnostics {
 306     use hir_expand::diagnostics::DiagnosticSink;
 307     use ra_db::RelativePathBuf;
 308     use ra_syntax::{ast, AstPtr};
 309
 310     use crate::{db::DefDatabase, diagnostics::UnresolvedModule, nameres::LocalModuleId, AstId};
 311
 312     #[derive(Debug, PartialEq, Eq)]
 313     pub(super) enum DefDiagnostic {
 314         UnresolvedModule {
 315             module: LocalModuleId,
 316             declaration: AstId<ast::Module>,
 317             candidate: RelativePathBuf,
 318         },
 319     }
 320
 321     impl DefDiagnostic {
 322         pub(super) fn add_to(
 323             &self,
 324             db: &impl DefDatabase,
 325             target_module: LocalModuleId,
 326             sink: &mut DiagnosticSink,
 327         ) {
 328             match self {
 329                 DefDiagnostic::UnresolvedModule { module, declaration, candidate } => {
 330                     if *module != target_module {
 331                         return;
 332                     }
 333                     let decl = declaration.to_node(db);
 334                     sink.push(UnresolvedModule {
 335                         file: declaration.file_id,
 336                         decl: AstPtr::new(&decl),
 337                         candidate: candidate.clone(),
 338                     })
 339                 }
 340             }
 341         }
 342     }
 343 }