crates/ra_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 hir_expand::{
   7     builtin_derive::find_builtin_derive,
   8     builtin_macro::find_builtin_macro,
   9     name::{name, AsName, Name},
  10     HirFileId, MacroCallId, MacroCallKind, MacroDefId, MacroDefKind,
  11 };
  12 use ra_cfg::CfgOptions;
  13 use ra_db::{CrateId, FileId};
  14 use ra_syntax::ast;
  15 use rustc_hash::FxHashMap;
  16 use test_utils::tested_by;
  17
  18 use crate::{
  19     attr::Attrs,
  20     db::DefDatabase,
  21     nameres::{
  22         diagnostics::DefDiagnostic, mod_resolution::ModDir, path_resolution::ReachedFixedPoint,
  23         raw, BuiltinShadowMode, CrateDefMap, ModuleData, ModuleOrigin, Resolution, ResolveMode,
  24     },
  25     path::{ModPath, PathKind},
  26     per_ns::PerNs,
  27     AdtId, AstId, ConstLoc, ContainerId, EnumLoc, EnumVariantId, FunctionLoc, ImplLoc, Intern,
  28     LocalImportId, LocalModuleId, ModuleDefId, ModuleId, StaticLoc, StructLoc, TraitLoc,
  29     TypeAliasLoc, UnionLoc,
  30 };
  31
  32 pub(super) fn collect_defs(db: &impl DefDatabase, mut def_map: CrateDefMap) -> CrateDefMap {
  33     let crate_graph = db.crate_graph();
  34
  35     // populate external prelude
  36     for dep in crate_graph.dependencies(def_map.krate) {
  37         let dep_def_map = db.crate_def_map(dep.crate_id);
  38         log::debug!("crate dep {:?} -> {:?}", dep.name, dep.crate_id);
  39         def_map.extern_prelude.insert(
  40             dep.as_name(),
  41             ModuleId { krate: dep.crate_id, local_id: dep_def_map.root }.into(),
  42         );
  43
  44         // look for the prelude
  45         // If the dependency defines a prelude, we overwrite an already defined
  46         // prelude. This is necessary to import the "std" prelude if a crate
  47         // depends on both "core" and "std".
  48         let dep_def_map = db.crate_def_map(dep.crate_id);
  49         if dep_def_map.prelude.is_some() {
  50             def_map.prelude = dep_def_map.prelude;
  51         }
  52     }
  53
  54     let cfg_options = crate_graph.cfg_options(def_map.krate);
  55
  56     let mut collector = DefCollector {
  57         db,
  58         def_map,
  59         glob_imports: FxHashMap::default(),
  60         unresolved_imports: Vec::new(),
  61         resolved_imports: Vec::new(),
  62
  63         unexpanded_macros: Vec::new(),
  64         unexpanded_attribute_macros: Vec::new(),
  65         mod_dirs: FxHashMap::default(),
  66         cfg_options,
  67     };
  68     collector.collect();
  69     collector.finish()
  70 }
  71
  72 #[derive(Copy, Clone, Debug, Eq, PartialEq)]
  73 enum PartialResolvedImport {
  74     /// None of any namespaces is resolved
  75     Unresolved,
  76     /// One of namespaces is resolved
  77     Indeterminate(PerNs),
  78     /// All namespaces are resolved, OR it is came from other crate
  79     Resolved(PerNs),
  80 }
  81
  82 impl PartialResolvedImport {
  83     fn namespaces(&self) -> PerNs {
  84         match self {
  85             PartialResolvedImport::Unresolved => PerNs::none(),
  86             PartialResolvedImport::Indeterminate(ns) => *ns,
  87             PartialResolvedImport::Resolved(ns) => *ns,
  88         }
  89     }
  90 }
  91
  92 #[derive(Clone, Debug, Eq, PartialEq)]
  93 struct ImportDirective {
  94     module_id: LocalModuleId,
  95     import_id: LocalImportId,
  96     import: raw::ImportData,
  97     status: PartialResolvedImport,
  98 }
  99
 100 #[derive(Clone, Debug, Eq, PartialEq)]
 101 struct MacroDirective {
 102     module_id: LocalModuleId,
 103     ast_id: AstId<ast::MacroCall>,
 104     path: ModPath,
 105     legacy: Option<MacroCallId>,
 106 }
 107
 108 /// Walks the tree of module recursively
 109 struct DefCollector<'a, DB> {
 110     db: &'a DB,
 111     def_map: CrateDefMap,
 112     glob_imports: FxHashMap<LocalModuleId, Vec<(LocalModuleId, LocalImportId)>>,
 113     unresolved_imports: Vec<ImportDirective>,
 114     resolved_imports: Vec<ImportDirective>,
 115     unexpanded_macros: Vec<MacroDirective>,
 116     unexpanded_attribute_macros: Vec<(LocalModuleId, AstId<ast::ModuleItem>, ModPath)>,
 117     mod_dirs: FxHashMap<LocalModuleId, ModDir>,
 118     cfg_options: &'a CfgOptions,
 119 }
 120
 121 impl<DB> DefCollector<'_, DB>
 122 where
 123     DB: DefDatabase,
 124 {
 125     fn collect(&mut self) {
 126         let crate_graph = self.db.crate_graph();
 127         let file_id = crate_graph.crate_root(self.def_map.krate);
 128         let raw_items = self.db.raw_items(file_id.into());
 129         let module_id = self.def_map.root;
 130         self.def_map.modules[module_id].origin = ModuleOrigin::CrateRoot { definition: file_id };
 131         ModCollector {
 132             def_collector: &mut *self,
 133             module_id,
 134             file_id: file_id.into(),
 135             raw_items: &raw_items,
 136             mod_dir: ModDir::root(),
 137         }
 138         .collect(raw_items.items());
 139
 140         // main name resolution fixed-point loop.
 141         let mut i = 0;
 142         loop {
 143             self.db.check_canceled();
 144             self.resolve_imports();
 145
 146             match self.resolve_macros() {
 147                 ReachedFixedPoint::Yes => break,
 148                 ReachedFixedPoint::No => i += 1,
 149             }
 150             if i == 1000 {
 151                 log::error!("name resolution is stuck");
 152                 break;
 153             }
 154         }
 155
 156         // Resolve all indeterminate resolved imports again
 157         // As some of the macros will expand newly import shadowing partial resolved imports
 158         // FIXME: We maybe could skip this, if we handle the Indetermine imports in `resolve_imports`
 159         // correctly
 160         let partial_resolved = self.resolved_imports.iter().filter_map(|directive| {
 161             if let PartialResolvedImport::Indeterminate(_) = directive.status {
 162                 let mut directive = directive.clone();
 163                 directive.status = PartialResolvedImport::Unresolved;
 164                 Some(directive)
 165             } else {
 166                 None
 167             }
 168         });
 169         self.unresolved_imports.extend(partial_resolved);
 170         self.resolve_imports();
 171
 172         let unresolved_imports = std::mem::replace(&mut self.unresolved_imports, Vec::new());
 173         // show unresolved imports in completion, etc
 174         for directive in unresolved_imports {
 175             self.record_resolved_import(&directive)
 176         }
 177     }
 178
 179     /// Define a macro with `macro_rules`.
 180     ///
 181     /// It will define the macro in legacy textual scope, and if it has `#[macro_export]`,
 182     /// then it is also defined in the root module scope.
 183     /// You can `use` or invoke it by `crate::macro_name` anywhere, before or after the definition.
 184     ///
 185     /// It is surprising that the macro will never be in the current module scope.
 186     /// These code fails with "unresolved import/macro",
 187     /// ```rust,compile_fail
 188     /// mod m { macro_rules! foo { () => {} } }
 189     /// use m::foo as bar;
 190     /// ```
 191     ///
 192     /// ```rust,compile_fail
 193     /// macro_rules! foo { () => {} }
 194     /// self::foo!();
 195     /// crate::foo!();
 196     /// ```
 197     ///
 198     /// Well, this code compiles, because the plain path `foo` in `use` is searched
 199     /// in the legacy textual scope only.
 200     /// ```rust
 201     /// macro_rules! foo { () => {} }
 202     /// use foo as bar;
 203     /// ```
 204     fn define_macro(
 205         &mut self,
 206         module_id: LocalModuleId,
 207         name: Name,
 208         macro_: MacroDefId,
 209         export: bool,
 210     ) {
 211         // Textual scoping
 212         self.define_legacy_macro(module_id, name.clone(), macro_);
 213
 214         // Module scoping
 215         // In Rust, `#[macro_export]` macros are unconditionally visible at the
 216         // crate root, even if the parent modules is **not** visible.
 217         if export {
 218             self.update(
 219                 self.def_map.root,
 220                 None,
 221                 &[(name, Resolution { def: PerNs::macros(macro_), import: None })],
 222             );
 223         }
 224     }
 225
 226     /// Define a legacy textual scoped macro in module
 227     ///
 228     /// We use a map `legacy_macros` to store all legacy textual scoped macros visable per module.
 229     /// It will clone all macros from parent legacy scope, whose definition is prior to
 230     /// the definition of current module.
 231     /// And also, `macro_use` on a module will import all legacy macros visable inside to
 232     /// current legacy scope, with possible shadowing.
 233     fn define_legacy_macro(&mut self, module_id: LocalModuleId, name: Name, macro_: MacroDefId) {
 234         // Always shadowing
 235         self.def_map.modules[module_id].scope.legacy_macros.insert(name, macro_);
 236     }
 237
 238     /// Import macros from `#[macro_use] extern crate`.
 239     fn import_macros_from_extern_crate(
 240         &mut self,
 241         current_module_id: LocalModuleId,
 242         import: &raw::ImportData,
 243     ) {
 244         log::debug!(
 245             "importing macros from extern crate: {:?} ({:?})",
 246             import,
 247             self.def_map.edition,
 248         );
 249
 250         let res = self.def_map.resolve_name_in_extern_prelude(
 251             &import
 252                 .path
 253                 .as_ident()
 254                 .expect("extern crate should have been desugared to one-element path"),
 255         );
 256
 257         if let Some(ModuleDefId::ModuleId(m)) = res.take_types() {
 258             tested_by!(macro_rules_from_other_crates_are_visible_with_macro_use);
 259             self.import_all_macros_exported(current_module_id, m.krate);
 260         }
 261     }
 262
 263     /// Import all exported macros from another crate
 264     ///
 265     /// Exported macros are just all macros in the root module scope.
 266     /// Note that it contains not only all `#[macro_export]` macros, but also all aliases
 267     /// created by `use` in the root module, ignoring the visibility of `use`.
 268     fn import_all_macros_exported(&mut self, current_module_id: LocalModuleId, krate: CrateId) {
 269         let def_map = self.db.crate_def_map(krate);
 270         for (name, def) in def_map[def_map.root].scope.macros() {
 271             // `macro_use` only bring things into legacy scope.
 272             self.define_legacy_macro(current_module_id, name.clone(), def);
 273         }
 274     }
 275
 276     /// Import resolution
 277     ///
 278     /// This is a fix point algorithm. We resolve imports until no forward
 279     /// progress in resolving imports is made
 280     fn resolve_imports(&mut self) {
 281         let mut n_previous_unresolved = self.unresolved_imports.len() + 1;
 282
 283         while self.unresolved_imports.len() < n_previous_unresolved {
 284             n_previous_unresolved = self.unresolved_imports.len();
 285             let imports = std::mem::replace(&mut self.unresolved_imports, Vec::new());
 286             for mut directive in imports {
 287                 directive.status = self.resolve_import(directive.module_id, &directive.import);
 288
 289                 match directive.status {
 290                     PartialResolvedImport::Indeterminate(_) => {
 291                         self.record_resolved_import(&directive);
 292                         // FIXME: For avoid performance regression,
 293                         // we consider an imported resolved if it is indeterminate (i.e not all namespace resolved)
 294                         self.resolved_imports.push(directive)
 295                     }
 296                     PartialResolvedImport::Resolved(_) => {
 297                         self.record_resolved_import(&directive);
 298                         self.resolved_imports.push(directive)
 299                     }
 300                     PartialResolvedImport::Unresolved => {
 301                         self.unresolved_imports.push(directive);
 302                     }
 303                 }
 304             }
 305         }
 306     }
 307
 308     fn resolve_import(
 309         &self,
 310         module_id: LocalModuleId,
 311         import: &raw::ImportData,
 312     ) -> PartialResolvedImport {
 313         log::debug!("resolving import: {:?} ({:?})", import, self.def_map.edition);
 314         if import.is_extern_crate {
 315             let res = self.def_map.resolve_name_in_extern_prelude(
 316                 &import
 317                     .path
 318                     .as_ident()
 319                     .expect("extern crate should have been desugared to one-element path"),
 320             );
 321             PartialResolvedImport::Resolved(res)
 322         } else {
 323             let res = self.def_map.resolve_path_fp_with_macro(
 324                 self.db,
 325                 ResolveMode::Import,
 326                 module_id,
 327                 &import.path,
 328                 BuiltinShadowMode::Module,
 329             );
 330
 331             let def = res.resolved_def;
 332             if res.reached_fixedpoint == ReachedFixedPoint::No {
 333                 return PartialResolvedImport::Unresolved;
 334             }
 335
 336             if let Some(krate) = res.krate {
 337                 if krate != self.def_map.krate {
 338                     return PartialResolvedImport::Resolved(def);
 339                 }
 340             }
 341
 342             // Check whether all namespace is resolved
 343             if def.take_types().is_some()
 344                 && def.take_values().is_some()
 345                 && def.take_macros().is_some()
 346             {
 347                 PartialResolvedImport::Resolved(def)
 348             } else {
 349                 PartialResolvedImport::Indeterminate(def)
 350             }
 351         }
 352     }
 353
 354     fn record_resolved_import(&mut self, directive: &ImportDirective) {
 355         let module_id = directive.module_id;
 356         let import_id = directive.import_id;
 357         let import = &directive.import;
 358         let def = directive.status.namespaces();
 359
 360         if import.is_glob {
 361             log::debug!("glob import: {:?}", import);
 362             match def.take_types() {
 363                 Some(ModuleDefId::ModuleId(m)) => {
 364                     if import.is_prelude {
 365                         tested_by!(std_prelude);
 366                         self.def_map.prelude = Some(m);
 367                     } else if m.krate != self.def_map.krate {
 368                         tested_by!(glob_across_crates);
 369                         // glob import from other crate => we can just import everything once
 370                         let item_map = self.db.crate_def_map(m.krate);
 371                         let scope = &item_map[m.local_id].scope;
 372
 373                         // Module scoped macros is included
 374                         let items = scope
 375                             .items
 376                             .iter()
 377                             .map(|(name, res)| (name.clone(), res.clone()))
 378                             .collect::<Vec<_>>();
 379
 380                         self.update(module_id, Some(import_id), &items);
 381                     } else {
 382                         // glob import from same crate => we do an initial
 383                         // import, and then need to propagate any further
 384                         // additions
 385                         let scope = &self.def_map[m.local_id].scope;
 386
 387                         // Module scoped macros is included
 388                         let items = scope
 389                             .items
 390                             .iter()
 391                             .map(|(name, res)| (name.clone(), res.clone()))
 392                             .collect::<Vec<_>>();
 393
 394                         self.update(module_id, Some(import_id), &items);
 395                         // record the glob import in case we add further items
 396                         let glob = self.glob_imports.entry(m.local_id).or_default();
 397                         if !glob.iter().any(|it| *it == (module_id, import_id)) {
 398                             glob.push((module_id, import_id));
 399                         }
 400                     }
 401                 }
 402                 Some(ModuleDefId::AdtId(AdtId::EnumId(e))) => {
 403                     tested_by!(glob_enum);
 404                     // glob import from enum => just import all the variants
 405                     let enum_data = self.db.enum_data(e);
 406                     let resolutions = enum_data
 407                         .variants
 408                         .iter()
 409                         .filter_map(|(local_id, variant_data)| {
 410                             let name = variant_data.name.clone();
 411                             let variant = EnumVariantId { parent: e, local_id };
 412                             let res = Resolution {
 413                                 def: PerNs::both(variant.into(), variant.into()),
 414                                 import: Some(import_id),
 415                             };
 416                             Some((name, res))
 417                         })
 418                         .collect::<Vec<_>>();
 419                     self.update(module_id, Some(import_id), &resolutions);
 420                 }
 421                 Some(d) => {
 422                     log::debug!("glob import {:?} from non-module/enum {:?}", import, d);
 423                 }
 424                 None => {
 425                     log::debug!("glob import {:?} didn't resolve as type", import);
 426                 }
 427             }
 428         } else {
 429             match import.path.segments.last() {
 430                 Some(last_segment) => {
 431                     let name = import.alias.clone().unwrap_or_else(|| last_segment.clone());
 432                     log::debug!("resolved import {:?} ({:?}) to {:?}", name, import, def);
 433
 434                     // extern crates in the crate root are special-cased to insert entries into the extern prelude: rust-lang/rust#54658
 435                     if import.is_extern_crate && module_id == self.def_map.root {
 436                         if let Some(def) = def.take_types() {
 437                             self.def_map.extern_prelude.insert(name.clone(), def);
 438                         }
 439                     }
 440
 441                     let resolution = Resolution { def, import: Some(import_id) };
 442                     self.update(module_id, Some(import_id), &[(name, resolution)]);
 443                 }
 444                 None => tested_by!(bogus_paths),
 445             }
 446         }
 447     }
 448
 449     fn update(
 450         &mut self,
 451         module_id: LocalModuleId,
 452         import: Option<LocalImportId>,
 453         resolutions: &[(Name, Resolution)],
 454     ) {
 455         self.update_recursive(module_id, import, resolutions, 0)
 456     }
 457
 458     fn update_recursive(
 459         &mut self,
 460         module_id: LocalModuleId,
 461         import: Option<LocalImportId>,
 462         resolutions: &[(Name, Resolution)],
 463         depth: usize,
 464     ) {
 465         if depth > 100 {
 466             // prevent stack overflows (but this shouldn't be possible)
 467             panic!("infinite recursion in glob imports!");
 468         }
 469         let module_items = &mut self.def_map.modules[module_id].scope;
 470         let mut changed = false;
 471         for (name, res) in resolutions {
 472             let existing = module_items.items.entry(name.clone()).or_default();
 473
 474             if existing.def.types.is_none() && res.def.types.is_some() {
 475                 existing.def.types = res.def.types;
 476                 existing.import = import.or(res.import);
 477                 changed = true;
 478             }
 479             if existing.def.values.is_none() && res.def.values.is_some() {
 480                 existing.def.values = res.def.values;
 481                 existing.import = import.or(res.import);
 482                 changed = true;
 483             }
 484             if existing.def.macros.is_none() && res.def.macros.is_some() {
 485                 existing.def.macros = res.def.macros;
 486                 existing.import = import.or(res.import);
 487                 changed = true;
 488             }
 489
 490             if existing.def.is_none()
 491                 && res.def.is_none()
 492                 && existing.import.is_none()
 493                 && res.import.is_some()
 494             {
 495                 existing.import = res.import;
 496             }
 497         }
 498
 499         if !changed {
 500             return;
 501         }
 502         let glob_imports = self
 503             .glob_imports
 504             .get(&module_id)
 505             .into_iter()
 506             .flat_map(|v| v.iter())
 507             .cloned()
 508             .collect::<Vec<_>>();
 509         for (glob_importing_module, glob_import) in glob_imports {
 510             // We pass the glob import so that the tracked import in those modules is that glob import
 511             self.update_recursive(glob_importing_module, Some(glob_import), resolutions, depth + 1);
 512         }
 513     }
 514
 515     fn resolve_macros(&mut self) -> ReachedFixedPoint {
 516         let mut macros = std::mem::replace(&mut self.unexpanded_macros, Vec::new());
 517         let mut attribute_macros =
 518             std::mem::replace(&mut self.unexpanded_attribute_macros, Vec::new());
 519         let mut resolved = Vec::new();
 520         let mut res = ReachedFixedPoint::Yes;
 521         macros.retain(|directive| {
 522             if let Some(call_id) = directive.legacy {
 523                 res = ReachedFixedPoint::No;
 524                 resolved.push((directive.module_id, call_id));
 525                 return false;
 526             }
 527
 528             let resolved_res = self.def_map.resolve_path_fp_with_macro(
 529                 self.db,
 530                 ResolveMode::Other,
 531                 directive.module_id,
 532                 &directive.path,
 533                 BuiltinShadowMode::Module,
 534             );
 535
 536             if let Some(def) = resolved_res.resolved_def.take_macros() {
 537                 let call_id = def.as_call_id(self.db, MacroCallKind::FnLike(directive.ast_id));
 538                 resolved.push((directive.module_id, call_id));
 539                 res = ReachedFixedPoint::No;
 540                 return false;
 541             }
 542
 543             true
 544         });
 545         attribute_macros.retain(|(module_id, ast_id, path)| {
 546             let resolved_res = self.resolve_attribute_macro(path);
 547
 548             if let Some(def) = resolved_res {
 549                 let call_id = def.as_call_id(self.db, MacroCallKind::Attr(*ast_id));
 550                 resolved.push((*module_id, call_id));
 551                 res = ReachedFixedPoint::No;
 552                 return false;
 553             }
 554
 555             true
 556         });
 557
 558         self.unexpanded_macros = macros;
 559         self.unexpanded_attribute_macros = attribute_macros;
 560
 561         for (module_id, macro_call_id) in resolved {
 562             self.collect_macro_expansion(module_id, macro_call_id);
 563         }
 564
 565         res
 566     }
 567
 568     fn resolve_attribute_macro(&self, path: &ModPath) -> Option<MacroDefId> {
 569         // FIXME this is currently super hacky, just enough to support the
 570         // built-in derives
 571         if let Some(name) = path.as_ident() {
 572             // FIXME this should actually be handled with the normal name
 573             // resolution; the std lib defines built-in stubs for the derives,
 574             // but these are new-style `macro`s, which we don't support yet
 575             if let Some(def_id) = find_builtin_derive(name) {
 576                 return Some(def_id);
 577             }
 578         }
 579         None
 580     }
 581
 582     fn collect_macro_expansion(&mut self, module_id: LocalModuleId, macro_call_id: MacroCallId) {
 583         let file_id: HirFileId = macro_call_id.as_file();
 584         let raw_items = self.db.raw_items(file_id);
 585         let mod_dir = self.mod_dirs[&module_id].clone();
 586         ModCollector {
 587             def_collector: &mut *self,
 588             file_id,
 589             module_id,
 590             raw_items: &raw_items,
 591             mod_dir,
 592         }
 593         .collect(raw_items.items());
 594     }
 595
 596     fn finish(self) -> CrateDefMap {
 597         self.def_map
 598     }
 599 }
 600
 601 /// Walks a single module, populating defs, imports and macros
 602 struct ModCollector<'a, D> {
 603     def_collector: D,
 604     module_id: LocalModuleId,
 605     file_id: HirFileId,
 606     raw_items: &'a raw::RawItems,
 607     mod_dir: ModDir,
 608 }
 609
 610 impl<DB> ModCollector<'_, &'_ mut DefCollector<'_, DB>>
 611 where
 612     DB: DefDatabase,
 613 {
 614     fn collect(&mut self, items: &[raw::RawItem]) {
 615         // Note: don't assert that inserted value is fresh: it's simply not true
 616         // for macros.
 617         self.def_collector.mod_dirs.insert(self.module_id, self.mod_dir.clone());
 618
 619         // Prelude module is always considered to be `#[macro_use]`.
 620         if let Some(prelude_module) = self.def_collector.def_map.prelude {
 621             if prelude_module.krate != self.def_collector.def_map.krate {
 622                 tested_by!(prelude_is_macro_use);
 623                 self.def_collector.import_all_macros_exported(self.module_id, prelude_module.krate);
 624             }
 625         }
 626
 627         // This should be processed eagerly instead of deferred to resolving.
 628         // `#[macro_use] extern crate` is hoisted to imports macros before collecting
 629         // any other items.
 630         for item in items {
 631             if self.is_cfg_enabled(&item.attrs) {
 632                 if let raw::RawItemKind::Import(import_id) = item.kind {
 633                     let import = self.raw_items[import_id].clone();
 634                     if import.is_extern_crate && import.is_macro_use {
 635                         self.def_collector.import_macros_from_extern_crate(self.module_id, &import);
 636                     }
 637                 }
 638             }
 639         }
 640
 641         for item in items {
 642             if self.is_cfg_enabled(&item.attrs) {
 643                 match item.kind {
 644                     raw::RawItemKind::Module(m) => {
 645                         self.collect_module(&self.raw_items[m], &item.attrs)
 646                     }
 647                     raw::RawItemKind::Import(import_id) => {
 648                         self.def_collector.unresolved_imports.push(ImportDirective {
 649                             module_id: self.module_id,
 650                             import_id,
 651                             import: self.raw_items[import_id].clone(),
 652                             status: PartialResolvedImport::Unresolved,
 653                         })
 654                     }
 655                     raw::RawItemKind::Def(def) => {
 656                         self.define_def(&self.raw_items[def], &item.attrs)
 657                     }
 658                     raw::RawItemKind::Macro(mac) => self.collect_macro(&self.raw_items[mac]),
 659                     raw::RawItemKind::Impl(imp) => {
 660                         let module = ModuleId {
 661                             krate: self.def_collector.def_map.krate,
 662                             local_id: self.module_id,
 663                         };
 664                         let ast_id = self.raw_items[imp].ast_id;
 665                         let impl_id =
 666                             ImplLoc { container: module, ast_id: AstId::new(self.file_id, ast_id) }
 667                                 .intern(self.def_collector.db);
 668                         self.def_collector.def_map.modules[self.module_id].impls.push(impl_id)
 669                     }
 670                 }
 671             }
 672         }
 673     }
 674
 675     fn collect_module(&mut self, module: &raw::ModuleData, attrs: &Attrs) {
 676         let path_attr = attrs.by_key("path").string_value();
 677         let is_macro_use = attrs.by_key("macro_use").exists();
 678         match module {
 679             // inline module, just recurse
 680             raw::ModuleData::Definition { name, items, ast_id } => {
 681                 let module_id =
 682                     self.push_child_module(name.clone(), AstId::new(self.file_id, *ast_id), None);
 683
 684                 ModCollector {
 685                     def_collector: &mut *self.def_collector,
 686                     module_id,
 687                     file_id: self.file_id,
 688                     raw_items: self.raw_items,
 689                     mod_dir: self.mod_dir.descend_into_definition(name, path_attr),
 690                 }
 691                 .collect(&*items);
 692                 if is_macro_use {
 693                     self.import_all_legacy_macros(module_id);
 694                 }
 695             }
 696             // out of line module, resolve, parse and recurse
 697             raw::ModuleData::Declaration { name, ast_id } => {
 698                 let ast_id = AstId::new(self.file_id, *ast_id);
 699                 match self.mod_dir.resolve_declaration(
 700                     self.def_collector.db,
 701                     self.file_id,
 702                     name,
 703                     path_attr,
 704                 ) {
 705                     Ok((file_id, mod_dir)) => {
 706                         let module_id = self.push_child_module(name.clone(), ast_id, Some(file_id));
 707                         let raw_items = self.def_collector.db.raw_items(file_id.into());
 708                         ModCollector {
 709                             def_collector: &mut *self.def_collector,
 710                             module_id,
 711                             file_id: file_id.into(),
 712                             raw_items: &raw_items,
 713                             mod_dir,
 714                         }
 715                         .collect(raw_items.items());
 716                         if is_macro_use {
 717                             self.import_all_legacy_macros(module_id);
 718                         }
 719                     }
 720                     Err(candidate) => self.def_collector.def_map.diagnostics.push(
 721                         DefDiagnostic::UnresolvedModule {
 722                             module: self.module_id,
 723                             declaration: ast_id,
 724                             candidate,
 725                         },
 726                     ),
 727                 };
 728             }
 729         }
 730     }
 731
 732     fn push_child_module(
 733         &mut self,
 734         name: Name,
 735         declaration: AstId<ast::Module>,
 736         definition: Option<FileId>,
 737     ) -> LocalModuleId {
 738         let modules = &mut self.def_collector.def_map.modules;
 739         let res = modules.alloc(ModuleData::default());
 740         modules[res].parent = Some(self.module_id);
 741         modules[res].origin = ModuleOrigin::not_sure_file(definition, declaration);
 742         modules[res].scope.legacy_macros = modules[self.module_id].scope.legacy_macros.clone();
 743         modules[self.module_id].children.insert(name.clone(), res);
 744         let resolution = Resolution {
 745             def: PerNs::types(
 746                 ModuleId { krate: self.def_collector.def_map.krate, local_id: res }.into(),
 747             ),
 748             import: None,
 749         };
 750         self.def_collector.update(self.module_id, None, &[(name, resolution)]);
 751         res
 752     }
 753
 754     fn define_def(&mut self, def: &raw::DefData, attrs: &Attrs) {
 755         let module = ModuleId { krate: self.def_collector.def_map.krate, local_id: self.module_id };
 756         // FIXME: check attrs to see if this is an attribute macro invocation;
 757         // in which case we don't add the invocation, just a single attribute
 758         // macro invocation
 759
 760         self.collect_derives(attrs, def);
 761
 762         let name = def.name.clone();
 763         let container = ContainerId::ModuleId(module);
 764         let def: PerNs = match def.kind {
 765             raw::DefKind::Function(ast_id) => {
 766                 let def = FunctionLoc {
 767                     container: container.into(),
 768                     ast_id: AstId::new(self.file_id, ast_id),
 769                 }
 770                 .intern(self.def_collector.db);
 771
 772                 PerNs::values(def.into())
 773             }
 774             raw::DefKind::Struct(ast_id) => {
 775                 let def = StructLoc { container, ast_id: AstId::new(self.file_id, ast_id) }
 776                     .intern(self.def_collector.db);
 777                 PerNs::both(def.into(), def.into())
 778             }
 779             raw::DefKind::Union(ast_id) => {
 780                 let def = UnionLoc { container, ast_id: AstId::new(self.file_id, ast_id) }
 781                     .intern(self.def_collector.db);
 782                 PerNs::both(def.into(), def.into())
 783             }
 784             raw::DefKind::Enum(ast_id) => {
 785                 let def = EnumLoc { container, ast_id: AstId::new(self.file_id, ast_id) }
 786                     .intern(self.def_collector.db);
 787                 PerNs::types(def.into())
 788             }
 789             raw::DefKind::Const(ast_id) => {
 790                 let def = ConstLoc {
 791                     container: container.into(),
 792                     ast_id: AstId::new(self.file_id, ast_id),
 793                 }
 794                 .intern(self.def_collector.db);
 795
 796                 PerNs::values(def.into())
 797             }
 798             raw::DefKind::Static(ast_id) => {
 799                 let def = StaticLoc { container: module, ast_id: AstId::new(self.file_id, ast_id) }
 800                     .intern(self.def_collector.db);
 801
 802                 PerNs::values(def.into())
 803             }
 804             raw::DefKind::Trait(ast_id) => {
 805                 let def = TraitLoc { container: module, ast_id: AstId::new(self.file_id, ast_id) }
 806                     .intern(self.def_collector.db);
 807
 808                 PerNs::types(def.into())
 809             }
 810             raw::DefKind::TypeAlias(ast_id) => {
 811                 let def = TypeAliasLoc {
 812                     container: container.into(),
 813                     ast_id: AstId::new(self.file_id, ast_id),
 814                 }
 815                 .intern(self.def_collector.db);
 816
 817                 PerNs::types(def.into())
 818             }
 819         };
 820         let resolution = Resolution { def, import: None };
 821         self.def_collector.update(self.module_id, None, &[(name, resolution)])
 822     }
 823
 824     fn collect_derives(&mut self, attrs: &Attrs, def: &raw::DefData) {
 825         for derive_subtree in attrs.by_key("derive").tt_values() {
 826             // for #[derive(Copy, Clone)], `derive_subtree` is the `(Copy, Clone)` subtree
 827             for tt in &derive_subtree.token_trees {
 828                 let ident = match &tt {
 829                     tt::TokenTree::Leaf(tt::Leaf::Ident(ident)) => ident,
 830                     tt::TokenTree::Leaf(tt::Leaf::Punct(_)) => continue, // , is ok
 831                     _ => continue, // anything else would be an error (which we currently ignore)
 832                 };
 833                 let path = ModPath::from_tt_ident(ident);
 834
 835                 let ast_id = AstId::new(self.file_id, def.kind.ast_id());
 836                 self.def_collector.unexpanded_attribute_macros.push((self.module_id, ast_id, path));
 837             }
 838         }
 839     }
 840
 841     fn collect_macro(&mut self, mac: &raw::MacroData) {
 842         let ast_id = AstId::new(self.file_id, mac.ast_id);
 843
 844         // Case 0: builtin macros
 845         if mac.builtin {
 846             if let Some(name) = &mac.name {
 847                 let krate = self.def_collector.def_map.krate;
 848                 if let Some(macro_id) = find_builtin_macro(name, krate, ast_id) {
 849                     self.def_collector.define_macro(
 850                         self.module_id,
 851                         name.clone(),
 852                         macro_id,
 853                         mac.export,
 854                     );
 855                     return;
 856                 }
 857             }
 858         }
 859
 860         // Case 1: macro rules, define a macro in crate-global mutable scope
 861         if is_macro_rules(&mac.path) {
 862             if let Some(name) = &mac.name {
 863                 let macro_id = MacroDefId {
 864                     ast_id: Some(ast_id),
 865                     krate: Some(self.def_collector.def_map.krate),
 866                     kind: MacroDefKind::Declarative,
 867                 };
 868                 self.def_collector.define_macro(self.module_id, name.clone(), macro_id, mac.export);
 869             }
 870             return;
 871         }
 872
 873         // Case 2: try to resolve in legacy scope and expand macro_rules
 874         if let Some(macro_def) = mac.path.as_ident().and_then(|name| {
 875             self.def_collector.def_map[self.module_id].scope.get_legacy_macro(&name)
 876         }) {
 877             let macro_call_id =
 878                 macro_def.as_call_id(self.def_collector.db, MacroCallKind::FnLike(ast_id));
 879
 880             self.def_collector.unexpanded_macros.push(MacroDirective {
 881                 module_id: self.module_id,
 882                 path: mac.path.clone(),
 883                 ast_id,
 884                 legacy: Some(macro_call_id),
 885             });
 886
 887             return;
 888         }
 889
 890         // Case 3: resolve in module scope, expand during name resolution.
 891         // We rewrite simple path `macro_name` to `self::macro_name` to force resolve in module scope only.
 892         let mut path = mac.path.clone();
 893         if path.is_ident() {
 894             path.kind = PathKind::Super(0);
 895         }
 896
 897         self.def_collector.unexpanded_macros.push(MacroDirective {
 898             module_id: self.module_id,
 899             path,
 900             ast_id,
 901             legacy: None,
 902         });
 903     }
 904
 905     fn import_all_legacy_macros(&mut self, module_id: LocalModuleId) {
 906         let macros = self.def_collector.def_map[module_id].scope.legacy_macros.clone();
 907         for (name, macro_) in macros {
 908             self.def_collector.define_legacy_macro(self.module_id, name.clone(), macro_);
 909         }
 910     }
 911
 912     fn is_cfg_enabled(&self, attrs: &Attrs) -> bool {
 913         // FIXME: handle cfg_attr :-)
 914         attrs
 915             .by_key("cfg")
 916             .tt_values()
 917             .all(|tt| self.def_collector.cfg_options.is_cfg_enabled(tt) != Some(false))
 918     }
 919 }
 920
 921 fn is_macro_rules(path: &ModPath) -> bool {
 922     path.as_ident() == Some(&name![macro_rules])
 923 }
 924
 925 #[cfg(test)]
 926 mod tests {
 927     use crate::{db::DefDatabase, test_db::TestDB};
 928     use ra_arena::Arena;
 929     use ra_db::{fixture::WithFixture, SourceDatabase};
 930
 931     use super::*;
 932
 933     fn do_collect_defs(db: &impl DefDatabase, def_map: CrateDefMap) -> CrateDefMap {
 934         let mut collector = DefCollector {
 935             db,
 936             def_map,
 937             glob_imports: FxHashMap::default(),
 938             unresolved_imports: Vec::new(),
 939             resolved_imports: Vec::new(),
 940             unexpanded_macros: Vec::new(),
 941             unexpanded_attribute_macros: Vec::new(),
 942             mod_dirs: FxHashMap::default(),
 943             cfg_options: &CfgOptions::default(),
 944         };
 945         collector.collect();
 946         collector.def_map
 947     }
 948
 949     fn do_resolve(code: &str) -> CrateDefMap {
 950         let (db, _file_id) = TestDB::with_single_file(&code);
 951         let krate = db.test_crate();
 952
 953         let def_map = {
 954             let edition = db.crate_graph().edition(krate);
 955             let mut modules: Arena<LocalModuleId, ModuleData> = Arena::default();
 956             let root = modules.alloc(ModuleData::default());
 957             CrateDefMap {
 958                 krate,
 959                 edition,
 960                 extern_prelude: FxHashMap::default(),
 961                 prelude: None,
 962                 root,
 963                 modules,
 964                 diagnostics: Vec::new(),
 965             }
 966         };
 967         do_collect_defs(&db, def_map)
 968     }
 969
 970     #[test]
 971     fn test_macro_expand_will_stop() {
 972         do_resolve(
 973             r#"
 974         macro_rules! foo {
 975             ($($ty:ty)*) => { foo!($($ty)*, $($ty)*); }
 976         }
 977 foo!(KABOOM);
 978         "#,
 979         );
 980     }
 981 }