crates/hir_def/src/nameres/collector.rs

   1 //! The core of the module-level name resolution algorithm.
   2 //!
   3 //! `DefCollector::collect` contains the fixed-point iteration loop which
   4 //! resolves imports and expands macros.
   5
   6 use std::iter;
   7
   8 use base_db::{CrateId, FileId, ProcMacroId};
   9 use cfg::{CfgExpr, CfgOptions};
  10 use hir_expand::{
  11     ast_id_map::FileAstId,
  12     builtin_derive::find_builtin_derive,
  13     builtin_macro::find_builtin_macro,
  14     name::{AsName, Name},
  15     proc_macro::ProcMacroExpander,
  16     HirFileId, MacroCallId, MacroCallKind, MacroDefId, MacroDefKind,
  17 };
  18 use hir_expand::{InFile, MacroCallLoc};
  19 use rustc_hash::{FxHashMap, FxHashSet};
  20 use syntax::ast;
  21 use test_utils::mark;
  22 use tt::{Leaf, TokenTree};
  23
  24 use crate::{
  25     attr::Attrs,
  26     db::DefDatabase,
  27     item_scope::{ImportType, PerNsGlobImports},
  28     item_tree::{
  29         self, FileItemTreeId, ItemTree, ItemTreeId, MacroCall, MacroRules, Mod, ModItem, ModKind,
  30         StructDefKind,
  31     },
  32     nameres::{
  33         diagnostics::DefDiagnostic, mod_resolution::ModDir, path_resolution::ReachedFixedPoint,
  34         BuiltinShadowMode, DefMap, ModuleData, ModuleOrigin, ResolveMode,
  35     },
  36     path::{ImportAlias, ModPath, PathKind},
  37     per_ns::PerNs,
  38     visibility::{RawVisibility, Visibility},
  39     AdtId, AsMacroCall, AstId, AstIdWithPath, ConstLoc, ContainerId, EnumLoc, EnumVariantId,
  40     FunctionLoc, ImplLoc, Intern, LocalModuleId, ModuleDefId, ModuleId, StaticLoc, StructLoc,
  41     TraitLoc, TypeAliasLoc, UnionLoc,
  42 };
  43
  44 const GLOB_RECURSION_LIMIT: usize = 100;
  45 const EXPANSION_DEPTH_LIMIT: usize = 128;
  46 const FIXED_POINT_LIMIT: usize = 8192;
  47
  48 pub(super) fn collect_defs(db: &dyn DefDatabase, mut def_map: DefMap) -> DefMap {
  49     let crate_graph = db.crate_graph();
  50
  51     // populate external prelude
  52     for dep in &crate_graph[def_map.krate].dependencies {
  53         log::debug!("crate dep {:?} -> {:?}", dep.name, dep.crate_id);
  54         let dep_def_map = db.crate_def_map(dep.crate_id);
  55         def_map.extern_prelude.insert(
  56             dep.as_name(),
  57             ModuleId { krate: dep.crate_id, local_id: dep_def_map.root }.into(),
  58         );
  59
  60         // look for the prelude
  61         // If the dependency defines a prelude, we overwrite an already defined
  62         // prelude. This is necessary to import the "std" prelude if a crate
  63         // depends on both "core" and "std".
  64         if dep_def_map.prelude.is_some() {
  65             def_map.prelude = dep_def_map.prelude;
  66         }
  67     }
  68
  69     let cfg_options = &crate_graph[def_map.krate].cfg_options;
  70     let proc_macros = &crate_graph[def_map.krate].proc_macro;
  71     let proc_macros = proc_macros
  72         .iter()
  73         .enumerate()
  74         .map(|(idx, it)| {
  75             // FIXME: a hacky way to create a Name from string.
  76             let name = tt::Ident { text: it.name.clone(), id: tt::TokenId::unspecified() };
  77             (name.as_name(), ProcMacroExpander::new(def_map.krate, ProcMacroId(idx as u32)))
  78         })
  79         .collect();
  80
  81     let mut collector = DefCollector {
  82         db,
  83         def_map,
  84         glob_imports: FxHashMap::default(),
  85         unresolved_imports: Vec::new(),
  86         resolved_imports: Vec::new(),
  87
  88         unexpanded_macros: Vec::new(),
  89         unexpanded_attribute_macros: Vec::new(),
  90         mod_dirs: FxHashMap::default(),
  91         cfg_options,
  92         proc_macros,
  93         exports_proc_macros: false,
  94         from_glob_import: Default::default(),
  95     };
  96     collector.collect();
  97     collector.finish()
  98 }
  99
 100 #[derive(Copy, Clone, Debug, Eq, PartialEq)]
 101 enum PartialResolvedImport {
 102     /// None of any namespaces is resolved
 103     Unresolved,
 104     /// One of namespaces is resolved
 105     Indeterminate(PerNs),
 106     /// All namespaces are resolved, OR it is came from other crate
 107     Resolved(PerNs),
 108 }
 109
 110 impl PartialResolvedImport {
 111     fn namespaces(&self) -> PerNs {
 112         match self {
 113             PartialResolvedImport::Unresolved => PerNs::none(),
 114             PartialResolvedImport::Indeterminate(ns) => *ns,
 115             PartialResolvedImport::Resolved(ns) => *ns,
 116         }
 117     }
 118 }
 119
 120 #[derive(Clone, Debug, Eq, PartialEq)]
 121 enum ImportSource {
 122     Import(ItemTreeId<item_tree::Import>),
 123     ExternCrate(ItemTreeId<item_tree::ExternCrate>),
 124 }
 125
 126 #[derive(Clone, Debug, Eq, PartialEq)]
 127 struct Import {
 128     path: ModPath,
 129     alias: Option<ImportAlias>,
 130     visibility: RawVisibility,
 131     is_glob: bool,
 132     is_prelude: bool,
 133     is_extern_crate: bool,
 134     is_macro_use: bool,
 135     source: ImportSource,
 136 }
 137
 138 impl Import {
 139     fn from_use(
 140         db: &dyn DefDatabase,
 141         krate: CrateId,
 142         tree: &ItemTree,
 143         id: ItemTreeId<item_tree::Import>,
 144     ) -> Self {
 145         let it = &tree[id.value];
 146         let attrs = &tree.attrs(db, krate, ModItem::from(id.value).into());
 147         let visibility = &tree[it.visibility];
 148         Self {
 149             path: it.path.clone(),
 150             alias: it.alias.clone(),
 151             visibility: visibility.clone(),
 152             is_glob: it.is_glob,
 153             is_prelude: attrs.by_key("prelude_import").exists(),
 154             is_extern_crate: false,
 155             is_macro_use: false,
 156             source: ImportSource::Import(id),
 157         }
 158     }
 159
 160     fn from_extern_crate(
 161         db: &dyn DefDatabase,
 162         krate: CrateId,
 163         tree: &ItemTree,
 164         id: ItemTreeId<item_tree::ExternCrate>,
 165     ) -> Self {
 166         let it = &tree[id.value];
 167         let attrs = &tree.attrs(db, krate, ModItem::from(id.value).into());
 168         let visibility = &tree[it.visibility];
 169         Self {
 170             path: ModPath::from_segments(PathKind::Plain, iter::once(it.name.clone())),
 171             alias: it.alias.clone(),
 172             visibility: visibility.clone(),
 173             is_glob: false,
 174             is_prelude: false,
 175             is_extern_crate: true,
 176             is_macro_use: attrs.by_key("macro_use").exists(),
 177             source: ImportSource::ExternCrate(id),
 178         }
 179     }
 180 }
 181
 182 #[derive(Clone, Debug, Eq, PartialEq)]
 183 struct ImportDirective {
 184     module_id: LocalModuleId,
 185     import: Import,
 186     status: PartialResolvedImport,
 187 }
 188
 189 #[derive(Clone, Debug, Eq, PartialEq)]
 190 struct MacroDirective {
 191     module_id: LocalModuleId,
 192     ast_id: AstIdWithPath<ast::MacroCall>,
 193     legacy: Option<MacroCallId>,
 194     depth: usize,
 195 }
 196
 197 #[derive(Clone, Debug, Eq, PartialEq)]
 198 struct DeriveDirective {
 199     module_id: LocalModuleId,
 200     ast_id: AstIdWithPath<ast::Item>,
 201 }
 202
 203 struct DefData<'a> {
 204     id: ModuleDefId,
 205     name: &'a Name,
 206     visibility: &'a RawVisibility,
 207     has_constructor: bool,
 208 }
 209
 210 /// Walks the tree of module recursively
 211 struct DefCollector<'a> {
 212     db: &'a dyn DefDatabase,
 213     def_map: DefMap,
 214     glob_imports: FxHashMap<LocalModuleId, Vec<(LocalModuleId, Visibility)>>,
 215     unresolved_imports: Vec<ImportDirective>,
 216     resolved_imports: Vec<ImportDirective>,
 217     unexpanded_macros: Vec<MacroDirective>,
 218     unexpanded_attribute_macros: Vec<DeriveDirective>,
 219     mod_dirs: FxHashMap<LocalModuleId, ModDir>,
 220     cfg_options: &'a CfgOptions,
 221     /// List of procedural macros defined by this crate. This is read from the dynamic library
 222     /// built by the build system, and is the list of proc. macros we can actually expand. It is
 223     /// empty when proc. macro support is disabled (in which case we still do name resolution for
 224     /// them).
 225     proc_macros: Vec<(Name, ProcMacroExpander)>,
 226     exports_proc_macros: bool,
 227     from_glob_import: PerNsGlobImports,
 228 }
 229
 230 impl DefCollector<'_> {
 231     fn collect(&mut self) {
 232         let file_id = self.db.crate_graph()[self.def_map.krate].root_file_id;
 233         let item_tree = self.db.item_tree(file_id.into());
 234         let module_id = self.def_map.root;
 235         self.def_map.modules[module_id].origin = ModuleOrigin::CrateRoot { definition: file_id };
 236         if item_tree
 237             .top_level_attrs(self.db, self.def_map.krate)
 238             .cfg()
 239             .map_or(true, |cfg| self.cfg_options.check(&cfg) != Some(false))
 240         {
 241             ModCollector {
 242                 def_collector: &mut *self,
 243                 macro_depth: 0,
 244                 module_id,
 245                 file_id: file_id.into(),
 246                 item_tree: &item_tree,
 247                 mod_dir: ModDir::root(),
 248             }
 249             .collect(item_tree.top_level_items());
 250         }
 251
 252         // main name resolution fixed-point loop.
 253         let mut i = 0;
 254         loop {
 255             self.db.check_canceled();
 256             self.resolve_imports();
 257
 258             match self.resolve_macros() {
 259                 ReachedFixedPoint::Yes => break,
 260                 ReachedFixedPoint::No => i += 1,
 261             }
 262             if i == FIXED_POINT_LIMIT {
 263                 log::error!("name resolution is stuck");
 264                 break;
 265             }
 266         }
 267
 268         // Resolve all indeterminate resolved imports again
 269         // As some of the macros will expand newly import shadowing partial resolved imports
 270         // FIXME: We maybe could skip this, if we handle the indeterminate imports in `resolve_imports`
 271         // correctly
 272         let partial_resolved = self.resolved_imports.iter().filter_map(|directive| {
 273             if let PartialResolvedImport::Indeterminate(_) = directive.status {
 274                 let mut directive = directive.clone();
 275                 directive.status = PartialResolvedImport::Unresolved;
 276                 Some(directive)
 277             } else {
 278                 None
 279             }
 280         });
 281         self.unresolved_imports.extend(partial_resolved);
 282         self.resolve_imports();
 283
 284         let unresolved_imports = std::mem::replace(&mut self.unresolved_imports, Vec::new());
 285         // show unresolved imports in completion, etc
 286         for directive in &unresolved_imports {
 287             self.record_resolved_import(directive)
 288         }
 289         self.unresolved_imports = unresolved_imports;
 290
 291         // FIXME: This condition should instead check if this is a `proc-macro` type crate.
 292         if self.exports_proc_macros {
 293             // A crate exporting procedural macros is not allowed to export anything else.
 294             //
 295             // Additionally, while the proc macro entry points must be `pub`, they are not publicly
 296             // exported in type/value namespace. This function reduces the visibility of all items
 297             // in the crate root that aren't proc macros.
 298             let root = self.def_map.root;
 299             let root = &mut self.def_map.modules[root];
 300             root.scope.censor_non_proc_macros(ModuleId {
 301                 krate: self.def_map.krate,
 302                 local_id: self.def_map.root,
 303             });
 304         }
 305     }
 306
 307     /// Adds a definition of procedural macro `name` to the root module.
 308     ///
 309     /// # Notes on procedural macro resolution
 310     ///
 311     /// Procedural macro functionality is provided by the build system: It has to build the proc
 312     /// macro and pass the resulting dynamic library to rust-analyzer.
 313     ///
 314     /// When procedural macro support is enabled, the list of proc macros exported by a crate is
 315     /// known before we resolve names in the crate. This list is stored in `self.proc_macros` and is
 316     /// derived from the dynamic library.
 317     ///
 318     /// However, we *also* would like to be able to at least *resolve* macros on our own, without
 319     /// help by the build system. So, when the macro isn't found in `self.proc_macros`, we instead
 320     /// use a dummy expander that always errors. This comes with the drawback of macros potentially
 321     /// going out of sync with what the build system sees (since we resolve using VFS state, but
 322     /// Cargo builds only on-disk files). We could and probably should add diagnostics for that.
 323     fn resolve_proc_macro(&mut self, name: &Name) {
 324         self.exports_proc_macros = true;
 325         let macro_def = match self.proc_macros.iter().find(|(n, _)| n == name) {
 326             Some((_, expander)) => MacroDefId {
 327                 ast_id: None,
 328                 krate: self.def_map.krate,
 329                 kind: MacroDefKind::ProcMacro(*expander),
 330                 local_inner: false,
 331             },
 332             None => MacroDefId {
 333                 ast_id: None,
 334                 krate: self.def_map.krate,
 335                 kind: MacroDefKind::ProcMacro(ProcMacroExpander::dummy(self.def_map.krate)),
 336                 local_inner: false,
 337             },
 338         };
 339
 340         self.define_proc_macro(name.clone(), macro_def);
 341     }
 342
 343     /// Define a macro with `macro_rules`.
 344     ///
 345     /// It will define the macro in legacy textual scope, and if it has `#[macro_export]`,
 346     /// then it is also defined in the root module scope.
 347     /// You can `use` or invoke it by `crate::macro_name` anywhere, before or after the definition.
 348     ///
 349     /// It is surprising that the macro will never be in the current module scope.
 350     /// These code fails with "unresolved import/macro",
 351     /// ```rust,compile_fail
 352     /// mod m { macro_rules! foo { () => {} } }
 353     /// use m::foo as bar;
 354     /// ```
 355     ///
 356     /// ```rust,compile_fail
 357     /// macro_rules! foo { () => {} }
 358     /// self::foo!();
 359     /// crate::foo!();
 360     /// ```
 361     ///
 362     /// Well, this code compiles, because the plain path `foo` in `use` is searched
 363     /// in the legacy textual scope only.
 364     /// ```rust
 365     /// macro_rules! foo { () => {} }
 366     /// use foo as bar;
 367     /// ```
 368     fn define_macro(
 369         &mut self,
 370         module_id: LocalModuleId,
 371         name: Name,
 372         macro_: MacroDefId,
 373         export: bool,
 374     ) {
 375         // Textual scoping
 376         self.define_legacy_macro(module_id, name.clone(), macro_);
 377
 378         // Module scoping
 379         // In Rust, `#[macro_export]` macros are unconditionally visible at the
 380         // crate root, even if the parent modules is **not** visible.
 381         if export {
 382             self.update(
 383                 self.def_map.root,
 384                 &[(Some(name), PerNs::macros(macro_, Visibility::Public))],
 385                 Visibility::Public,
 386                 ImportType::Named,
 387             );
 388         }
 389     }
 390
 391     /// Define a legacy textual scoped macro in module
 392     ///
 393     /// We use a map `legacy_macros` to store all legacy textual scoped macros visible per module.
 394     /// It will clone all macros from parent legacy scope, whose definition is prior to
 395     /// the definition of current module.
 396     /// And also, `macro_use` on a module will import all legacy macros visible inside to
 397     /// current legacy scope, with possible shadowing.
 398     fn define_legacy_macro(&mut self, module_id: LocalModuleId, name: Name, mac: MacroDefId) {
 399         // Always shadowing
 400         self.def_map.modules[module_id].scope.define_legacy_macro(name, mac);
 401     }
 402
 403     /// Define a proc macro
 404     ///
 405     /// A proc macro is similar to normal macro scope, but it would not visible in legacy textual scoped.
 406     /// And unconditionally exported.
 407     fn define_proc_macro(&mut self, name: Name, macro_: MacroDefId) {
 408         self.update(
 409             self.def_map.root,
 410             &[(Some(name), PerNs::macros(macro_, Visibility::Public))],
 411             Visibility::Public,
 412             ImportType::Named,
 413         );
 414     }
 415
 416     /// Import macros from `#[macro_use] extern crate`.
 417     fn import_macros_from_extern_crate(
 418         &mut self,
 419         current_module_id: LocalModuleId,
 420         extern_crate: &item_tree::ExternCrate,
 421     ) {
 422         log::debug!(
 423             "importing macros from extern crate: {:?} ({:?})",
 424             extern_crate,
 425             self.def_map.edition,
 426         );
 427
 428         let res = self.def_map.resolve_name_in_extern_prelude(&extern_crate.name);
 429
 430         if let Some(ModuleDefId::ModuleId(m)) = res.take_types() {
 431             mark::hit!(macro_rules_from_other_crates_are_visible_with_macro_use);
 432             self.import_all_macros_exported(current_module_id, m.krate);
 433         }
 434     }
 435
 436     /// Import all exported macros from another crate
 437     ///
 438     /// Exported macros are just all macros in the root module scope.
 439     /// Note that it contains not only all `#[macro_export]` macros, but also all aliases
 440     /// created by `use` in the root module, ignoring the visibility of `use`.
 441     fn import_all_macros_exported(&mut self, current_module_id: LocalModuleId, krate: CrateId) {
 442         let def_map = self.db.crate_def_map(krate);
 443         for (name, def) in def_map[def_map.root].scope.macros() {
 444             // `macro_use` only bring things into legacy scope.
 445             self.define_legacy_macro(current_module_id, name.clone(), def);
 446         }
 447     }
 448
 449     /// Import resolution
 450     ///
 451     /// This is a fix point algorithm. We resolve imports until no forward
 452     /// progress in resolving imports is made
 453     fn resolve_imports(&mut self) {
 454         let mut n_previous_unresolved = self.unresolved_imports.len() + 1;
 455
 456         while self.unresolved_imports.len() < n_previous_unresolved {
 457             n_previous_unresolved = self.unresolved_imports.len();
 458             let imports = std::mem::replace(&mut self.unresolved_imports, Vec::new());
 459             for mut directive in imports {
 460                 directive.status = self.resolve_import(directive.module_id, &directive.import);
 461                 match directive.status {
 462                     PartialResolvedImport::Indeterminate(_) => {
 463                         self.record_resolved_import(&directive);
 464                         // FIXME: For avoid performance regression,
 465                         // we consider an imported resolved if it is indeterminate (i.e not all namespace resolved)
 466                         self.resolved_imports.push(directive)
 467                     }
 468                     PartialResolvedImport::Resolved(_) => {
 469                         self.record_resolved_import(&directive);
 470                         self.resolved_imports.push(directive)
 471                     }
 472                     PartialResolvedImport::Unresolved => {
 473                         self.unresolved_imports.push(directive);
 474                     }
 475                 }
 476             }
 477         }
 478     }
 479
 480     fn resolve_import(&self, module_id: LocalModuleId, import: &Import) -> PartialResolvedImport {
 481         log::debug!("resolving import: {:?} ({:?})", import, self.def_map.edition);
 482         if import.is_extern_crate {
 483             let res = self.def_map.resolve_name_in_extern_prelude(
 484                 &import
 485                     .path
 486                     .as_ident()
 487                     .expect("extern crate should have been desugared to one-element path"),
 488             );
 489             if res.is_none() {
 490                 PartialResolvedImport::Unresolved
 491             } else {
 492                 PartialResolvedImport::Resolved(res)
 493             }
 494         } else {
 495             let res = self.def_map.resolve_path_fp_with_macro(
 496                 self.db,
 497                 ResolveMode::Import,
 498                 module_id,
 499                 &import.path,
 500                 BuiltinShadowMode::Module,
 501             );
 502
 503             let def = res.resolved_def;
 504             if res.reached_fixedpoint == ReachedFixedPoint::No || def.is_none() {
 505                 return PartialResolvedImport::Unresolved;
 506             }
 507
 508             if let Some(krate) = res.krate {
 509                 if krate != self.def_map.krate {
 510                     return PartialResolvedImport::Resolved(def);
 511                 }
 512             }
 513
 514             // Check whether all namespace is resolved
 515             if def.take_types().is_some()
 516                 && def.take_values().is_some()
 517                 && def.take_macros().is_some()
 518             {
 519                 PartialResolvedImport::Resolved(def)
 520             } else {
 521                 PartialResolvedImport::Indeterminate(def)
 522             }
 523         }
 524     }
 525
 526     fn record_resolved_import(&mut self, directive: &ImportDirective) {
 527         let module_id = directive.module_id;
 528         let import = &directive.import;
 529         let def = directive.status.namespaces();
 530         let vis = self
 531             .def_map
 532             .resolve_visibility(self.db, module_id, &directive.import.visibility)
 533             .unwrap_or(Visibility::Public);
 534
 535         if import.is_glob {
 536             log::debug!("glob import: {:?}", import);
 537             match def.take_types() {
 538                 Some(ModuleDefId::ModuleId(m)) => {
 539                     if import.is_prelude {
 540                         mark::hit!(std_prelude);
 541                         self.def_map.prelude = Some(m);
 542                     } else if m.krate != self.def_map.krate {
 543                         mark::hit!(glob_across_crates);
 544                         // glob import from other crate => we can just import everything once
 545                         let item_map = self.db.crate_def_map(m.krate);
 546                         let scope = &item_map[m.local_id].scope;
 547
 548                         // Module scoped macros is included
 549                         let items = scope
 550                             .resolutions()
 551                             // only keep visible names...
 552                             .map(|(n, res)| {
 553                                 (n, res.filter_visibility(|v| v.is_visible_from_other_crate()))
 554                             })
 555                             .filter(|(_, res)| !res.is_none())
 556                             .collect::<Vec<_>>();
 557
 558                         self.update(module_id, &items, vis, ImportType::Glob);
 559                     } else {
 560                         // glob import from same crate => we do an initial
 561                         // import, and then need to propagate any further
 562                         // additions
 563                         let scope = &self.def_map[m.local_id].scope;
 564
 565                         // Module scoped macros is included
 566                         let items = scope
 567                             .resolutions()
 568                             // only keep visible names...
 569                             .map(|(n, res)| {
 570                                 (
 571                                     n,
 572                                     res.filter_visibility(|v| {
 573                                         v.is_visible_from_def_map(&self.def_map, module_id)
 574                                     }),
 575                                 )
 576                             })
 577                             .filter(|(_, res)| !res.is_none())
 578                             .collect::<Vec<_>>();
 579
 580                         self.update(module_id, &items, vis, ImportType::Glob);
 581                         // record the glob import in case we add further items
 582                         let glob = self.glob_imports.entry(m.local_id).or_default();
 583                         if !glob.iter().any(|(mid, _)| *mid == module_id) {
 584                             glob.push((module_id, vis));
 585                         }
 586                     }
 587                 }
 588                 Some(ModuleDefId::AdtId(AdtId::EnumId(e))) => {
 589                     mark::hit!(glob_enum);
 590                     // glob import from enum => just import all the variants
 591
 592                     // XXX: urgh, so this works by accident! Here, we look at
 593                     // the enum data, and, in theory, this might require us to
 594                     // look back at the crate_def_map, creating a cycle. For
 595                     // example, `enum E { crate::some_macro!(); }`. Luckily, the
 596                     // only kind of macro that is allowed inside enum is a
 597                     // `cfg_macro`, and we don't need to run name resolution for
 598                     // it, but this is sheer luck!
 599                     let enum_data = self.db.enum_data(e);
 600                     let resolutions = enum_data
 601                         .variants
 602                         .iter()
 603                         .map(|(local_id, variant_data)| {
 604                             let name = variant_data.name.clone();
 605                             let variant = EnumVariantId { parent: e, local_id };
 606                             let res = PerNs::both(variant.into(), variant.into(), vis);
 607                             (Some(name), res)
 608                         })
 609                         .collect::<Vec<_>>();
 610                     self.update(module_id, &resolutions, vis, ImportType::Glob);
 611                 }
 612                 Some(d) => {
 613                     log::debug!("glob import {:?} from non-module/enum {:?}", import, d);
 614                 }
 615                 None => {
 616                     log::debug!("glob import {:?} didn't resolve as type", import);
 617                 }
 618             }
 619         } else {
 620             match import.path.segments.last() {
 621                 Some(last_segment) => {
 622                     let name = match &import.alias {
 623                         Some(ImportAlias::Alias(name)) => Some(name.clone()),
 624                         Some(ImportAlias::Underscore) => None,
 625                         None => Some(last_segment.clone()),
 626                     };
 627                     log::debug!("resolved import {:?} ({:?}) to {:?}", name, import, def);
 628
 629                     // extern crates in the crate root are special-cased to insert entries into the extern prelude: rust-lang/rust#54658
 630                     if import.is_extern_crate && module_id == self.def_map.root {
 631                         if let (Some(def), Some(name)) = (def.take_types(), name.as_ref()) {
 632                             self.def_map.extern_prelude.insert(name.clone(), def);
 633                         }
 634                     }
 635
 636                     self.update(module_id, &[(name, def)], vis, ImportType::Named);
 637                 }
 638                 None => mark::hit!(bogus_paths),
 639             }
 640         }
 641     }
 642
 643     fn update(
 644         &mut self,
 645         module_id: LocalModuleId,
 646         resolutions: &[(Option<Name>, PerNs)],
 647         vis: Visibility,
 648         import_type: ImportType,
 649     ) {
 650         self.db.check_canceled();
 651         self.update_recursive(module_id, resolutions, vis, import_type, 0)
 652     }
 653
 654     fn update_recursive(
 655         &mut self,
 656         module_id: LocalModuleId,
 657         resolutions: &[(Option<Name>, PerNs)],
 658         // All resolutions are imported with this visibility; the visibilities in
 659         // the `PerNs` values are ignored and overwritten
 660         vis: Visibility,
 661         import_type: ImportType,
 662         depth: usize,
 663     ) {
 664         if depth > GLOB_RECURSION_LIMIT {
 665             // prevent stack overflows (but this shouldn't be possible)
 666             panic!("infinite recursion in glob imports!");
 667         }
 668         let mut changed = false;
 669
 670         for (name, res) in resolutions {
 671             match name {
 672                 Some(name) => {
 673                     let scope = &mut self.def_map.modules[module_id].scope;
 674                     changed |= scope.push_res_with_import(
 675                         &mut self.from_glob_import,
 676                         (module_id, name.clone()),
 677                         res.with_visibility(vis),
 678                         import_type,
 679                     );
 680                 }
 681                 None => {
 682                     let tr = match res.take_types() {
 683                         Some(ModuleDefId::TraitId(tr)) => tr,
 684                         Some(other) => {
 685                             log::debug!("non-trait `_` import of {:?}", other);
 686                             continue;
 687                         }
 688                         None => continue,
 689                     };
 690                     let old_vis = self.def_map.modules[module_id].scope.unnamed_trait_vis(tr);
 691                     let should_update = match old_vis {
 692                         None => true,
 693                         Some(old_vis) => {
 694                             let max_vis = old_vis.max(vis, &self.def_map).unwrap_or_else(|| {
 695                                 panic!("`Tr as _` imports with unrelated visibilities {:?} and {:?} (trait {:?})", old_vis, vis, tr);
 696                             });
 697
 698                             if max_vis == old_vis {
 699                                 false
 700                             } else {
 701                                 mark::hit!(upgrade_underscore_visibility);
 702                                 true
 703                             }
 704                         }
 705                     };
 706
 707                     if should_update {
 708                         changed = true;
 709                         self.def_map.modules[module_id].scope.push_unnamed_trait(tr, vis);
 710                     }
 711                 }
 712             }
 713         }
 714
 715         if !changed {
 716             return;
 717         }
 718         let glob_imports = self
 719             .glob_imports
 720             .get(&module_id)
 721             .into_iter()
 722             .flat_map(|v| v.iter())
 723             .filter(|(glob_importing_module, _)| {
 724                 // we know all resolutions have the same visibility (`vis`), so we
 725                 // just need to check that once
 726                 vis.is_visible_from_def_map(&self.def_map, *glob_importing_module)
 727             })
 728             .cloned()
 729             .collect::<Vec<_>>();
 730
 731         for (glob_importing_module, glob_import_vis) in glob_imports {
 732             self.update_recursive(
 733                 glob_importing_module,
 734                 resolutions,
 735                 glob_import_vis,
 736                 ImportType::Glob,
 737                 depth + 1,
 738             );
 739         }
 740     }
 741
 742     fn resolve_macros(&mut self) -> ReachedFixedPoint {
 743         let mut macros = std::mem::replace(&mut self.unexpanded_macros, Vec::new());
 744         let mut attribute_macros =
 745             std::mem::replace(&mut self.unexpanded_attribute_macros, Vec::new());
 746         let mut resolved = Vec::new();
 747         let mut res = ReachedFixedPoint::Yes;
 748         macros.retain(|directive| {
 749             if let Some(call_id) = directive.legacy {
 750                 res = ReachedFixedPoint::No;
 751                 resolved.push((directive.module_id, call_id, directive.depth));
 752                 return false;
 753             }
 754
 755             if let Some(call_id) =
 756                 directive.ast_id.as_call_id(self.db, self.def_map.krate, |path| {
 757                     let resolved_res = self.def_map.resolve_path_fp_with_macro(
 758                         self.db,
 759                         ResolveMode::Other,
 760                         directive.module_id,
 761                         &path,
 762                         BuiltinShadowMode::Module,
 763                     );
 764                     resolved_res.resolved_def.take_macros()
 765                 })
 766             {
 767                 resolved.push((directive.module_id, call_id, directive.depth));
 768                 res = ReachedFixedPoint::No;
 769                 return false;
 770             }
 771
 772             true
 773         });
 774         attribute_macros.retain(|directive| {
 775             if let Some(call_id) =
 776                 directive.ast_id.as_call_id(self.db, self.def_map.krate, |path| {
 777                     self.resolve_attribute_macro(&directive, &path)
 778                 })
 779             {
 780                 resolved.push((directive.module_id, call_id, 0));
 781                 res = ReachedFixedPoint::No;
 782                 return false;
 783             }
 784
 785             true
 786         });
 787
 788         self.unexpanded_macros = macros;
 789         self.unexpanded_attribute_macros = attribute_macros;
 790
 791         for (module_id, macro_call_id, depth) in resolved {
 792             self.collect_macro_expansion(module_id, macro_call_id, depth);
 793         }
 794
 795         res
 796     }
 797
 798     fn resolve_attribute_macro(
 799         &self,
 800         directive: &DeriveDirective,
 801         path: &ModPath,
 802     ) -> Option<MacroDefId> {
 803         let resolved_res = self.def_map.resolve_path_fp_with_macro(
 804             self.db,
 805             ResolveMode::Other,
 806             directive.module_id,
 807             &path,
 808             BuiltinShadowMode::Module,
 809         );
 810
 811         resolved_res.resolved_def.take_macros()
 812     }
 813
 814     fn collect_macro_expansion(
 815         &mut self,
 816         module_id: LocalModuleId,
 817         macro_call_id: MacroCallId,
 818         depth: usize,
 819     ) {
 820         if depth > EXPANSION_DEPTH_LIMIT {
 821             mark::hit!(macro_expansion_overflow);
 822             log::warn!("macro expansion is too deep");
 823             return;
 824         }
 825         let file_id = macro_call_id.as_file();
 826
 827         // First, fetch the raw expansion result for purposes of error reporting. This goes through
 828         // `macro_expand_error` to avoid depending on the full expansion result (to improve
 829         // incrementality).
 830         let err = self.db.macro_expand_error(macro_call_id);
 831         if let Some(err) = err {
 832             if let MacroCallId::LazyMacro(id) = macro_call_id {
 833                 let loc: MacroCallLoc = self.db.lookup_intern_macro(id);
 834
 835                 let diag = match err {
 836                     hir_expand::ExpandError::UnresolvedProcMacro => {
 837                         // Missing proc macros are non-fatal, so they are handled specially.
 838                         DefDiagnostic::unresolved_proc_macro(module_id, loc.kind)
 839                     }
 840                     _ => DefDiagnostic::macro_error(module_id, loc.kind, err.to_string()),
 841                 };
 842
 843                 self.def_map.diagnostics.push(diag);
 844             }
 845             // FIXME: Handle eager macros.
 846         }
 847
 848         // Then, fetch and process the item tree. This will reuse the expansion result from above.
 849         let item_tree = self.db.item_tree(file_id);
 850         let mod_dir = self.mod_dirs[&module_id].clone();
 851         ModCollector {
 852             def_collector: &mut *self,
 853             macro_depth: depth,
 854             file_id,
 855             module_id,
 856             item_tree: &item_tree,
 857             mod_dir,
 858         }
 859         .collect(item_tree.top_level_items());
 860     }
 861
 862     fn finish(mut self) -> DefMap {
 863         // Emit diagnostics for all remaining unexpanded macros.
 864
 865         for directive in &self.unexpanded_macros {
 866             let mut error = None;
 867             directive.ast_id.as_call_id_with_errors(
 868                 self.db,
 869                 self.def_map.krate,
 870                 |path| {
 871                     let resolved_res = self.def_map.resolve_path_fp_with_macro(
 872                         self.db,
 873                         ResolveMode::Other,
 874                         directive.module_id,
 875                         &path,
 876                         BuiltinShadowMode::Module,
 877                     );
 878                     resolved_res.resolved_def.take_macros()
 879                 },
 880                 &mut |e| {
 881                     error.get_or_insert(e);
 882                 },
 883             );
 884
 885             if let Some(err) = error {
 886                 self.def_map.diagnostics.push(DefDiagnostic::macro_error(
 887                     directive.module_id,
 888                     MacroCallKind::FnLike(directive.ast_id.ast_id),
 889                     err.to_string(),
 890                 ));
 891             }
 892         }
 893
 894         // Emit diagnostics for all remaining unresolved imports.
 895
 896         // We'd like to avoid emitting a diagnostics avalanche when some `extern crate` doesn't
 897         // resolve. We first emit diagnostics for unresolved extern crates and collect the missing
 898         // crate names. Then we emit diagnostics for unresolved imports, but only if the import
 899         // doesn't start with an unresolved crate's name. Due to renaming and reexports, this is a
 900         // heuristic, but it works in practice.
 901         let mut diagnosed_extern_crates = FxHashSet::default();
 902         for directive in &self.unresolved_imports {
 903             if let ImportSource::ExternCrate(krate) = directive.import.source {
 904                 let item_tree = self.db.item_tree(krate.file_id);
 905                 let extern_crate = &item_tree[krate.value];
 906
 907                 diagnosed_extern_crates.insert(extern_crate.name.clone());
 908
 909                 self.def_map.diagnostics.push(DefDiagnostic::unresolved_extern_crate(
 910                     directive.module_id,
 911                     InFile::new(krate.file_id, extern_crate.ast_id),
 912                 ));
 913             }
 914         }
 915
 916         for directive in &self.unresolved_imports {
 917             if let ImportSource::Import(import) = &directive.import.source {
 918                 let item_tree = self.db.item_tree(import.file_id);
 919                 let import_data = &item_tree[import.value];
 920
 921                 match (import_data.path.segments.first(), &import_data.path.kind) {
 922                     (Some(krate), PathKind::Plain) | (Some(krate), PathKind::Abs) => {
 923                         if diagnosed_extern_crates.contains(krate) {
 924                             continue;
 925                         }
 926                     }
 927                     _ => {}
 928                 }
 929
 930                 self.def_map.diagnostics.push(DefDiagnostic::unresolved_import(
 931                     directive.module_id,
 932                     InFile::new(import.file_id, import_data.ast_id),
 933                     import_data.index,
 934                 ));
 935             }
 936         }
 937
 938         self.def_map
 939     }
 940 }
 941
 942 /// Walks a single module, populating defs, imports and macros
 943 struct ModCollector<'a, 'b> {
 944     def_collector: &'a mut DefCollector<'b>,
 945     macro_depth: usize,
 946     module_id: LocalModuleId,
 947     file_id: HirFileId,
 948     item_tree: &'a ItemTree,
 949     mod_dir: ModDir,
 950 }
 951
 952 impl ModCollector<'_, '_> {
 953     fn collect(&mut self, items: &[ModItem]) {
 954         let krate = self.def_collector.def_map.krate;
 955
 956         // Note: don't assert that inserted value is fresh: it's simply not true
 957         // for macros.
 958         self.def_collector.mod_dirs.insert(self.module_id, self.mod_dir.clone());
 959
 960         // Prelude module is always considered to be `#[macro_use]`.
 961         if let Some(prelude_module) = self.def_collector.def_map.prelude {
 962             if prelude_module.krate != self.def_collector.def_map.krate {
 963                 mark::hit!(prelude_is_macro_use);
 964                 self.def_collector.import_all_macros_exported(self.module_id, prelude_module.krate);
 965             }
 966         }
 967
 968         // This should be processed eagerly instead of deferred to resolving.
 969         // `#[macro_use] extern crate` is hoisted to imports macros before collecting
 970         // any other items.
 971         for item in items {
 972             let attrs = self.item_tree.attrs(self.def_collector.db, krate, (*item).into());
 973             if attrs.cfg().map_or(true, |cfg| self.is_cfg_enabled(&cfg)) {
 974                 if let ModItem::ExternCrate(id) = item {
 975                     let import = self.item_tree[*id].clone();
 976                     let attrs = self.item_tree.attrs(
 977                         self.def_collector.db,
 978                         krate,
 979                         ModItem::from(*id).into(),
 980                     );
 981                     if attrs.by_key("macro_use").exists() {
 982                         self.def_collector.import_macros_from_extern_crate(self.module_id, &import);
 983                     }
 984                 }
 985             }
 986         }
 987
 988         for &item in items {
 989             let attrs = self.item_tree.attrs(self.def_collector.db, krate, item.into());
 990             if let Some(cfg) = attrs.cfg() {
 991                 if !self.is_cfg_enabled(&cfg) {
 992                     self.emit_unconfigured_diagnostic(item, &cfg);
 993                     continue;
 994                 }
 995             }
 996             let module =
 997                 ModuleId { krate: self.def_collector.def_map.krate, local_id: self.module_id };
 998             let container = ContainerId::ModuleId(module);
 999
1000             let mut def = None;
1001             match item {
1002                 ModItem::Mod(m) => self.collect_module(&self.item_tree[m], &attrs),
1003                 ModItem::Import(import_id) => {
1004                     self.def_collector.unresolved_imports.push(ImportDirective {
1005                         module_id: self.module_id,
1006                         import: Import::from_use(
1007                             self.def_collector.db,
1008                             krate,
1009                             &self.item_tree,
1010                             InFile::new(self.file_id, import_id),
1011                         ),
1012                         status: PartialResolvedImport::Unresolved,
1013                     })
1014                 }
1015                 ModItem::ExternCrate(import_id) => {
1016                     self.def_collector.unresolved_imports.push(ImportDirective {
1017                         module_id: self.module_id,
1018                         import: Import::from_extern_crate(
1019                             self.def_collector.db,
1020                             krate,
1021                             &self.item_tree,
1022                             InFile::new(self.file_id, import_id),
1023                         ),
1024                         status: PartialResolvedImport::Unresolved,
1025                     })
1026                 }
1027                 ModItem::MacroCall(mac) => self.collect_macro_call(&self.item_tree[mac]),
1028                 ModItem::MacroRules(id) => self.collect_macro_rules(id),
1029                 ModItem::MacroDef(id) => {
1030                     let mac = &self.item_tree[id];
1031                     let ast_id = InFile::new(self.file_id, mac.ast_id.upcast());
1032
1033                     // "Macro 2.0" is not currently supported by rust-analyzer, but libcore uses it
1034                     // to define builtin macros, so we support at least that part.
1035                     let attrs = self.item_tree.attrs(
1036                         self.def_collector.db,
1037                         krate,
1038                         ModItem::from(id).into(),
1039                     );
1040                     if attrs.by_key("rustc_builtin_macro").exists() {
1041                         let krate = self.def_collector.def_map.krate;
1042                         let macro_id = find_builtin_macro(&mac.name, krate, ast_id)
1043                             .or_else(|| find_builtin_derive(&mac.name, krate, ast_id));
1044                         if let Some(macro_id) = macro_id {
1045                             let vis = self
1046                                 .def_collector
1047                                 .def_map
1048                                 .resolve_visibility(
1049                                     self.def_collector.db,
1050                                     self.module_id,
1051                                     &self.item_tree[mac.visibility],
1052                                 )
1053                                 .unwrap_or(Visibility::Public);
1054                             self.def_collector.update(
1055                                 self.module_id,
1056                                 &[(Some(mac.name.clone()), PerNs::macros(macro_id, vis))],
1057                                 vis,
1058                                 ImportType::Named,
1059                             );
1060                         }
1061                     }
1062                 }
1063                 ModItem::Impl(imp) => {
1064                     let module = ModuleId {
1065                         krate: self.def_collector.def_map.krate,
1066                         local_id: self.module_id,
1067                     };
1068                     let container = ContainerId::ModuleId(module);
1069                     let impl_id = ImplLoc { container, id: ItemTreeId::new(self.file_id, imp) }
1070                         .intern(self.def_collector.db);
1071                     self.def_collector.def_map.modules[self.module_id].scope.define_impl(impl_id)
1072                 }
1073                 ModItem::Function(id) => {
1074                     let func = &self.item_tree[id];
1075
1076                     self.collect_proc_macro_def(&func.name, &attrs);
1077
1078                     def = Some(DefData {
1079                         id: FunctionLoc {
1080                             container: container.into(),
1081                             id: ItemTreeId::new(self.file_id, id),
1082                         }
1083                         .intern(self.def_collector.db)
1084                         .into(),
1085                         name: &func.name,
1086                         visibility: &self.item_tree[func.visibility],
1087                         has_constructor: false,
1088                     });
1089                 }
1090                 ModItem::Struct(id) => {
1091                     let it = &self.item_tree[id];
1092
1093                     // FIXME: check attrs to see if this is an attribute macro invocation;
1094                     // in which case we don't add the invocation, just a single attribute
1095                     // macro invocation
1096                     self.collect_derives(&attrs, it.ast_id.upcast());
1097
1098                     def = Some(DefData {
1099                         id: StructLoc { container, id: ItemTreeId::new(self.file_id, id) }
1100                             .intern(self.def_collector.db)
1101                             .into(),
1102                         name: &it.name,
1103                         visibility: &self.item_tree[it.visibility],
1104                         has_constructor: it.kind != StructDefKind::Record,
1105                     });
1106                 }
1107                 ModItem::Union(id) => {
1108                     let it = &self.item_tree[id];
1109
1110                     // FIXME: check attrs to see if this is an attribute macro invocation;
1111                     // in which case we don't add the invocation, just a single attribute
1112                     // macro invocation
1113                     self.collect_derives(&attrs, it.ast_id.upcast());
1114
1115                     def = Some(DefData {
1116                         id: UnionLoc { container, id: ItemTreeId::new(self.file_id, id) }
1117                             .intern(self.def_collector.db)
1118                             .into(),
1119                         name: &it.name,
1120                         visibility: &self.item_tree[it.visibility],
1121                         has_constructor: false,
1122                     });
1123                 }
1124                 ModItem::Enum(id) => {
1125                     let it = &self.item_tree[id];
1126
1127                     // FIXME: check attrs to see if this is an attribute macro invocation;
1128                     // in which case we don't add the invocation, just a single attribute
1129                     // macro invocation
1130                     self.collect_derives(&attrs, it.ast_id.upcast());
1131
1132                     def = Some(DefData {
1133                         id: EnumLoc { container, id: ItemTreeId::new(self.file_id, id) }
1134                             .intern(self.def_collector.db)
1135                             .into(),
1136                         name: &it.name,
1137                         visibility: &self.item_tree[it.visibility],
1138                         has_constructor: false,
1139                     });
1140                 }
1141                 ModItem::Const(id) => {
1142                     let it = &self.item_tree[id];
1143
1144                     if let Some(name) = &it.name {
1145                         def = Some(DefData {
1146                             id: ConstLoc {
1147                                 container: container.into(),
1148                                 id: ItemTreeId::new(self.file_id, id),
1149                             }
1150                             .intern(self.def_collector.db)
1151                             .into(),
1152                             name,
1153                             visibility: &self.item_tree[it.visibility],
1154                             has_constructor: false,
1155                         });
1156                     }
1157                 }
1158                 ModItem::Static(id) => {
1159                     let it = &self.item_tree[id];
1160
1161                     def = Some(DefData {
1162                         id: StaticLoc { container, id: ItemTreeId::new(self.file_id, id) }
1163                             .intern(self.def_collector.db)
1164                             .into(),
1165                         name: &it.name,
1166                         visibility: &self.item_tree[it.visibility],
1167                         has_constructor: false,
1168                     });
1169                 }
1170                 ModItem::Trait(id) => {
1171                     let it = &self.item_tree[id];
1172
1173                     def = Some(DefData {
1174                         id: TraitLoc { container, id: ItemTreeId::new(self.file_id, id) }
1175                             .intern(self.def_collector.db)
1176                             .into(),
1177                         name: &it.name,
1178                         visibility: &self.item_tree[it.visibility],
1179                         has_constructor: false,
1180                     });
1181                 }
1182                 ModItem::TypeAlias(id) => {
1183                     let it = &self.item_tree[id];
1184
1185                     def = Some(DefData {
1186                         id: TypeAliasLoc {
1187                             container: container.into(),
1188                             id: ItemTreeId::new(self.file_id, id),
1189                         }
1190                         .intern(self.def_collector.db)
1191                         .into(),
1192                         name: &it.name,
1193                         visibility: &self.item_tree[it.visibility],
1194                         has_constructor: false,
1195                     });
1196                 }
1197             }
1198
1199             if let Some(DefData { id, name, visibility, has_constructor }) = def {
1200                 self.def_collector.def_map.modules[self.module_id].scope.define_def(id);
1201                 let vis = self
1202                     .def_collector
1203                     .def_map
1204                     .resolve_visibility(self.def_collector.db, self.module_id, visibility)
1205                     .unwrap_or(Visibility::Public);
1206                 self.def_collector.update(
1207                     self.module_id,
1208                     &[(Some(name.clone()), PerNs::from_def(id, vis, has_constructor))],
1209                     vis,
1210                     ImportType::Named,
1211                 )
1212             }
1213         }
1214     }
1215
1216     fn collect_module(&mut self, module: &Mod, attrs: &Attrs) {
1217         let path_attr = attrs.by_key("path").string_value();
1218         let is_macro_use = attrs.by_key("macro_use").exists();
1219         match &module.kind {
1220             // inline module, just recurse
1221             ModKind::Inline { items } => {
1222                 let module_id = self.push_child_module(
1223                     module.name.clone(),
1224                     AstId::new(self.file_id, module.ast_id),
1225                     None,
1226                     &self.item_tree[module.visibility],
1227                 );
1228
1229                 if let Some(mod_dir) = self.mod_dir.descend_into_definition(&module.name, path_attr)
1230                 {
1231                     ModCollector {
1232                         def_collector: &mut *self.def_collector,
1233                         macro_depth: self.macro_depth,
1234                         module_id,
1235                         file_id: self.file_id,
1236                         item_tree: self.item_tree,
1237                         mod_dir,
1238                     }
1239                     .collect(&*items);
1240                     if is_macro_use {
1241                         self.import_all_legacy_macros(module_id);
1242                     }
1243                 }
1244             }
1245             // out of line module, resolve, parse and recurse
1246             ModKind::Outline {} => {
1247                 let ast_id = AstId::new(self.file_id, module.ast_id);
1248                 match self.mod_dir.resolve_declaration(
1249                     self.def_collector.db,
1250                     self.file_id,
1251                     &module.name,
1252                     path_attr,
1253                 ) {
1254                     Ok((file_id, is_mod_rs, mod_dir)) => {
1255                         let module_id = self.push_child_module(
1256                             module.name.clone(),
1257                             ast_id,
1258                             Some((file_id, is_mod_rs)),
1259                             &self.item_tree[module.visibility],
1260                         );
1261                         let item_tree = self.def_collector.db.item_tree(file_id.into());
1262                         ModCollector {
1263                             def_collector: &mut *self.def_collector,
1264                             macro_depth: self.macro_depth,
1265                             module_id,
1266                             file_id: file_id.into(),
1267                             item_tree: &item_tree,
1268                             mod_dir,
1269                         }
1270                         .collect(item_tree.top_level_items());
1271                         if is_macro_use {
1272                             self.import_all_legacy_macros(module_id);
1273                         }
1274                     }
1275                     Err(candidate) => {
1276                         self.def_collector.def_map.diagnostics.push(
1277                             DefDiagnostic::unresolved_module(self.module_id, ast_id, candidate),
1278                         );
1279                     }
1280                 };
1281             }
1282         }
1283     }
1284
1285     fn push_child_module(
1286         &mut self,
1287         name: Name,
1288         declaration: AstId<ast::Module>,
1289         definition: Option<(FileId, bool)>,
1290         visibility: &crate::visibility::RawVisibility,
1291     ) -> LocalModuleId {
1292         let vis = self
1293             .def_collector
1294             .def_map
1295             .resolve_visibility(self.def_collector.db, self.module_id, visibility)
1296             .unwrap_or(Visibility::Public);
1297         let modules = &mut self.def_collector.def_map.modules;
1298         let res = modules.alloc(ModuleData::default());
1299         modules[res].parent = Some(self.module_id);
1300         modules[res].origin = match definition {
1301             None => ModuleOrigin::Inline { definition: declaration },
1302             Some((definition, is_mod_rs)) => {
1303                 ModuleOrigin::File { declaration, definition, is_mod_rs }
1304             }
1305         };
1306         for (name, mac) in modules[self.module_id].scope.collect_legacy_macros() {
1307             modules[res].scope.define_legacy_macro(name, mac)
1308         }
1309         modules[self.module_id].children.insert(name.clone(), res);
1310         let module = ModuleId { krate: self.def_collector.def_map.krate, local_id: res };
1311         let def: ModuleDefId = module.into();
1312         self.def_collector.def_map.modules[self.module_id].scope.define_def(def);
1313         self.def_collector.update(
1314             self.module_id,
1315             &[(Some(name), PerNs::from_def(def, vis, false))],
1316             vis,
1317             ImportType::Named,
1318         );
1319         res
1320     }
1321
1322     fn collect_derives(&mut self, attrs: &Attrs, ast_id: FileAstId<ast::Item>) {
1323         for derive in attrs.by_key("derive").attrs() {
1324             match derive.parse_derive() {
1325                 Some(derive_macros) => {
1326                     for path in derive_macros {
1327                         let ast_id = AstIdWithPath::new(self.file_id, ast_id, path);
1328                         self.def_collector
1329                             .unexpanded_attribute_macros
1330                             .push(DeriveDirective { module_id: self.module_id, ast_id });
1331                     }
1332                 }
1333                 None => {
1334                     // FIXME: diagnose
1335                     log::debug!("malformed derive: {:?}", derive);
1336                 }
1337             }
1338         }
1339     }
1340
1341     /// If `attrs` registers a procedural macro, collects its definition.
1342     fn collect_proc_macro_def(&mut self, func_name: &Name, attrs: &Attrs) {
1343         // FIXME: this should only be done in the root module of `proc-macro` crates, not everywhere
1344         // FIXME: distinguish the type of macro
1345         let macro_name = if attrs.by_key("proc_macro").exists()
1346             || attrs.by_key("proc_macro_attribute").exists()
1347         {
1348             func_name.clone()
1349         } else {
1350             let derive = attrs.by_key("proc_macro_derive");
1351             if let Some(arg) = derive.tt_values().next() {
1352                 if let [TokenTree::Leaf(Leaf::Ident(trait_name)), ..] = &*arg.token_trees {
1353                     trait_name.as_name()
1354                 } else {
1355                     log::trace!("malformed `#[proc_macro_derive]`: {}", arg);
1356                     return;
1357                 }
1358             } else {
1359                 return;
1360             }
1361         };
1362
1363         self.def_collector.resolve_proc_macro(&macro_name);
1364     }
1365
1366     fn collect_macro_rules(&mut self, id: FileItemTreeId<MacroRules>) {
1367         let krate = self.def_collector.def_map.krate;
1368         let mac = &self.item_tree[id];
1369         let attrs = self.item_tree.attrs(self.def_collector.db, krate, ModItem::from(id).into());
1370         let ast_id = InFile::new(self.file_id, mac.ast_id.upcast());
1371
1372         let export_attr = attrs.by_key("macro_export");
1373
1374         let is_export = export_attr.exists();
1375         let is_local_inner = if is_export {
1376             export_attr.tt_values().map(|it| &it.token_trees).flatten().any(|it| match it {
1377                 tt::TokenTree::Leaf(tt::Leaf::Ident(ident)) => {
1378                     ident.text.contains("local_inner_macros")
1379                 }
1380                 _ => false,
1381             })
1382         } else {
1383             false
1384         };
1385
1386         // Case 1: builtin macros
1387         if attrs.by_key("rustc_builtin_macro").exists() {
1388             let krate = self.def_collector.def_map.krate;
1389             if let Some(macro_id) = find_builtin_macro(&mac.name, krate, ast_id) {
1390                 self.def_collector.define_macro(
1391                     self.module_id,
1392                     mac.name.clone(),
1393                     macro_id,
1394                     is_export,
1395                 );
1396                 return;
1397             }
1398         }
1399
1400         // Case 2: normal `macro_rules!` macro
1401         let macro_id = MacroDefId {
1402             ast_id: Some(ast_id),
1403             krate: self.def_collector.def_map.krate,
1404             kind: MacroDefKind::Declarative,
1405             local_inner: is_local_inner,
1406         };
1407         self.def_collector.define_macro(self.module_id, mac.name.clone(), macro_id, is_export);
1408     }
1409
1410     fn collect_macro_call(&mut self, mac: &MacroCall) {
1411         let mut ast_id = AstIdWithPath::new(self.file_id, mac.ast_id, mac.path.clone());
1412
1413         // Case 1: try to resolve in legacy scope and expand macro_rules
1414         if let Some(macro_call_id) =
1415             ast_id.as_call_id(self.def_collector.db, self.def_collector.def_map.krate, |path| {
1416                 path.as_ident().and_then(|name| {
1417                     self.def_collector.def_map[self.module_id].scope.get_legacy_macro(&name)
1418                 })
1419             })
1420         {
1421             self.def_collector.unexpanded_macros.push(MacroDirective {
1422                 module_id: self.module_id,
1423                 ast_id,
1424                 legacy: Some(macro_call_id),
1425                 depth: self.macro_depth + 1,
1426             });
1427
1428             return;
1429         }
1430
1431         // Case 2: resolve in module scope, expand during name resolution.
1432         // We rewrite simple path `macro_name` to `self::macro_name` to force resolve in module scope only.
1433         if ast_id.path.is_ident() {
1434             ast_id.path.kind = PathKind::Super(0);
1435         }
1436
1437         self.def_collector.unexpanded_macros.push(MacroDirective {
1438             module_id: self.module_id,
1439             ast_id,
1440             legacy: None,
1441             depth: self.macro_depth + 1,
1442         });
1443     }
1444
1445     fn import_all_legacy_macros(&mut self, module_id: LocalModuleId) {
1446         let macros = self.def_collector.def_map[module_id].scope.collect_legacy_macros();
1447         for (name, macro_) in macros {
1448             self.def_collector.define_legacy_macro(self.module_id, name.clone(), macro_);
1449         }
1450     }
1451
1452     fn is_cfg_enabled(&self, cfg: &CfgExpr) -> bool {
1453         self.def_collector.cfg_options.check(cfg) != Some(false)
1454     }
1455
1456     fn emit_unconfigured_diagnostic(&mut self, item: ModItem, cfg: &CfgExpr) {
1457         let ast_id = item.ast_id(self.item_tree);
1458
1459         let ast_id = InFile::new(self.file_id, ast_id);
1460         self.def_collector.def_map.diagnostics.push(DefDiagnostic::unconfigured_code(
1461             self.module_id,
1462             ast_id,
1463             cfg.clone(),
1464             self.def_collector.cfg_options.clone(),
1465         ));
1466     }
1467 }
1468
1469 #[cfg(test)]
1470 mod tests {
1471     use crate::{db::DefDatabase, test_db::TestDB};
1472     use base_db::{fixture::WithFixture, SourceDatabase};
1473     use la_arena::Arena;
1474
1475     use super::*;
1476
1477     fn do_collect_defs(db: &dyn DefDatabase, def_map: DefMap) -> DefMap {
1478         let mut collector = DefCollector {
1479             db,
1480             def_map,
1481             glob_imports: FxHashMap::default(),
1482             unresolved_imports: Vec::new(),
1483             resolved_imports: Vec::new(),
1484             unexpanded_macros: Vec::new(),
1485             unexpanded_attribute_macros: Vec::new(),
1486             mod_dirs: FxHashMap::default(),
1487             cfg_options: &CfgOptions::default(),
1488             proc_macros: Default::default(),
1489             exports_proc_macros: false,
1490             from_glob_import: Default::default(),
1491         };
1492         collector.collect();
1493         collector.def_map
1494     }
1495
1496     fn do_resolve(code: &str) -> DefMap {
1497         let (db, _file_id) = TestDB::with_single_file(&code);
1498         let krate = db.test_crate();
1499
1500         let def_map = {
1501             let edition = db.crate_graph()[krate].edition;
1502             let mut modules: Arena<ModuleData> = Arena::default();
1503             let root = modules.alloc(ModuleData::default());
1504             DefMap {
1505                 krate,
1506                 edition,
1507                 extern_prelude: FxHashMap::default(),
1508                 prelude: None,
1509                 root,
1510                 modules,
1511                 diagnostics: Vec::new(),
1512             }
1513         };
1514         do_collect_defs(&db, def_map)
1515     }
1516
1517     #[test]
1518     fn test_macro_expand_will_stop_1() {
1519         do_resolve(
1520             r#"
1521         macro_rules! foo {
1522             ($($ty:ty)*) => { foo!($($ty)*); }
1523         }
1524         foo!(KABOOM);
1525         "#,
1526         );
1527     }
1528
1529     #[ignore] // this test does succeed, but takes quite a while :/
1530     #[test]
1531     fn test_macro_expand_will_stop_2() {
1532         do_resolve(
1533             r#"
1534         macro_rules! foo {
1535             ($($ty:ty)*) => { foo!($($ty)* $($ty)*); }
1536         }
1537         foo!(KABOOM);
1538         "#,
1539         );
1540     }
1541 }