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