crates/hir_def/src/nameres.rs

   1 //! This module implements import-resolution/macro expansion algorithm.
   2 //!
   3 //! The result of this module is `CrateDefMap`: a data structure which contains:
   4 //!
   5 //!   * a tree of modules for the crate
   6 //!   * for each module, a set of items visible in the module (directly declared
   7 //!     or imported)
   8 //!
   9 //! Note that `CrateDefMap` contains fully macro expanded code.
  10 //!
  11 //! Computing `CrateDefMap` can be partitioned into several logically
  12 //! independent "phases". The phases are mutually recursive though, there's no
  13 //! strict ordering.
  14 //!
  15 //! ## Collecting RawItems
  16 //!
  17 //! This happens in the `raw` module, which parses a single source file into a
  18 //! set of top-level items. Nested imports are desugared to flat imports in this
  19 //! phase. Macro calls are represented as a triple of (Path, Option<Name>,
  20 //! TokenTree).
  21 //!
  22 //! ## Collecting Modules
  23 //!
  24 //! This happens in the `collector` module. In this phase, we recursively walk
  25 //! tree of modules, collect raw items from submodules, populate module scopes
  26 //! with defined items (so, we assign item ids in this phase) and record the set
  27 //! of unresolved imports and macros.
  28 //!
  29 //! While we walk tree of modules, we also record macro_rules definitions and
  30 //! expand calls to macro_rules defined macros.
  31 //!
  32 //! ## Resolving Imports
  33 //!
  34 //! We maintain a list of currently unresolved imports. On every iteration, we
  35 //! try to resolve some imports from this list. If the import is resolved, we
  36 //! record it, by adding an item to current module scope and, if necessary, by
  37 //! recursively populating glob imports.
  38 //!
  39 //! ## Resolving Macros
  40 //!
  41 //! macro_rules from the same crate use a global mutable namespace. We expand
  42 //! them immediately, when we collect modules.
  43 //!
  44 //! Macros from other crates (including proc-macros) can be used with
  45 //! `foo::bar!` syntax. We handle them similarly to imports. There's a list of
  46 //! unexpanded macros. On every iteration, we try to resolve each macro call
  47 //! path and, upon success, we run macro expansion and "collect module" phase on
  48 //! the result
  49
  50 mod collector;
  51 mod mod_resolution;
  52 mod path_resolution;
  53
  54 #[cfg(test)]
  55 mod tests;
  56
  57 use std::sync::Arc;
  58
  59 use base_db::{CrateId, Edition, FileId};
  60 use hir_expand::{diagnostics::DiagnosticSink, name::Name, InFile};
  61 use la_arena::Arena;
  62 use profile::Count;
  63 use rustc_hash::FxHashMap;
  64 use stdx::format_to;
  65 use syntax::{ast, AstNode};
  66
  67 use crate::{
  68     db::DefDatabase,
  69     item_scope::{BuiltinShadowMode, ItemScope},
  70     nameres::{diagnostics::DefDiagnostic, path_resolution::ResolveMode},
  71     path::ModPath,
  72     per_ns::PerNs,
  73     AstId, LocalModuleId, ModuleDefId, ModuleId,
  74 };
  75
  76 /// Contains all top-level defs from a macro-expanded crate
  77 #[derive(Debug, PartialEq, Eq)]
  78 pub struct DefMap {
  79     _c: Count<Self>,
  80     parent: Option<Arc<DefMap>>,
  81     root: LocalModuleId,
  82     modules: Arena<ModuleData>,
  83     krate: CrateId,
  84     /// The prelude module for this crate. This either comes from an import
  85     /// marked with the `prelude_import` attribute, or (in the normal case) from
  86     /// a dependency (`std` or `core`).
  87     prelude: Option<ModuleId>,
  88     extern_prelude: FxHashMap<Name, ModuleDefId>,
  89
  90     edition: Edition,
  91     diagnostics: Vec<DefDiagnostic>,
  92 }
  93
  94 impl std::ops::Index<LocalModuleId> for DefMap {
  95     type Output = ModuleData;
  96     fn index(&self, id: LocalModuleId) -> &ModuleData {
  97         &self.modules[id]
  98     }
  99 }
 100
 101 #[derive(Debug, PartialEq, Eq, Clone, Copy, Hash)]
 102 pub enum ModuleOrigin {
 103     CrateRoot {
 104         definition: FileId,
 105     },
 106     /// Note that non-inline modules, by definition, live inside non-macro file.
 107     File {
 108         is_mod_rs: bool,
 109         declaration: AstId<ast::Module>,
 110         definition: FileId,
 111     },
 112     Inline {
 113         definition: AstId<ast::Module>,
 114     },
 115     /// Pseudo-module introduced by a block scope (contains only inner items).
 116     BlockExpr {
 117         block: AstId<ast::BlockExpr>,
 118     },
 119 }
 120
 121 impl Default for ModuleOrigin {
 122     fn default() -> Self {
 123         ModuleOrigin::CrateRoot { definition: FileId(0) }
 124     }
 125 }
 126
 127 impl ModuleOrigin {
 128     fn declaration(&self) -> Option<AstId<ast::Module>> {
 129         match self {
 130             ModuleOrigin::File { declaration: module, .. }
 131             | ModuleOrigin::Inline { definition: module, .. } => Some(*module),
 132             ModuleOrigin::CrateRoot { .. } | ModuleOrigin::BlockExpr { .. } => None,
 133         }
 134     }
 135
 136     pub fn file_id(&self) -> Option<FileId> {
 137         match self {
 138             ModuleOrigin::File { definition, .. } | ModuleOrigin::CrateRoot { definition } => {
 139                 Some(*definition)
 140             }
 141             _ => None,
 142         }
 143     }
 144
 145     pub fn is_inline(&self) -> bool {
 146         match self {
 147             ModuleOrigin::Inline { .. } | ModuleOrigin::BlockExpr { .. } => true,
 148             ModuleOrigin::CrateRoot { .. } | ModuleOrigin::File { .. } => false,
 149         }
 150     }
 151
 152     /// Returns a node which defines this module.
 153     /// That is, a file or a `mod foo {}` with items.
 154     fn definition_source(&self, db: &dyn DefDatabase) -> InFile<ModuleSource> {
 155         match self {
 156             ModuleOrigin::File { definition, .. } | ModuleOrigin::CrateRoot { definition } => {
 157                 let file_id = *definition;
 158                 let sf = db.parse(file_id).tree();
 159                 InFile::new(file_id.into(), ModuleSource::SourceFile(sf))
 160             }
 161             ModuleOrigin::Inline { definition } => InFile::new(
 162                 definition.file_id,
 163                 ModuleSource::Module(definition.to_node(db.upcast())),
 164             ),
 165             ModuleOrigin::BlockExpr { block } => {
 166                 InFile::new(block.file_id, ModuleSource::BlockExpr(block.to_node(db.upcast())))
 167             }
 168         }
 169     }
 170 }
 171
 172 #[derive(Default, Debug, PartialEq, Eq)]
 173 pub struct ModuleData {
 174     pub parent: Option<LocalModuleId>,
 175     pub children: FxHashMap<Name, LocalModuleId>,
 176     pub scope: ItemScope,
 177
 178     /// Where does this module come from?
 179     pub origin: ModuleOrigin,
 180 }
 181
 182 impl DefMap {
 183     pub(crate) fn crate_def_map_query(db: &dyn DefDatabase, krate: CrateId) -> Arc<DefMap> {
 184         let _p = profile::span("crate_def_map_query").detail(|| {
 185             db.crate_graph()[krate].display_name.as_deref().unwrap_or_default().to_string()
 186         });
 187         let edition = db.crate_graph()[krate].edition;
 188         let def_map = DefMap::empty(krate, edition);
 189         let def_map = collector::collect_defs(db, def_map, None);
 190         Arc::new(def_map)
 191     }
 192
 193     pub(crate) fn block_def_map_query(
 194         db: &dyn DefDatabase,
 195         krate: CrateId,
 196         block: AstId<ast::BlockExpr>,
 197     ) -> Arc<DefMap> {
 198         let item_tree = db.item_tree(block.file_id);
 199         let block_items = item_tree.inner_items_of_block(block.value);
 200
 201         let parent = parent_def_map(db, krate, block);
 202
 203         if block_items.is_empty() {
 204             // If there are no inner items, nothing new is brought into scope, so we can just return
 205             // the parent DefMap. This keeps DefMap parent chains short.
 206             return parent;
 207         }
 208
 209         let mut def_map = DefMap::empty(krate, parent.edition);
 210         def_map.parent = Some(parent);
 211
 212         let def_map = collector::collect_defs(db, def_map, Some(block.value));
 213         Arc::new(def_map)
 214     }
 215
 216     fn empty(krate: CrateId, edition: Edition) -> DefMap {
 217         let mut modules: Arena<ModuleData> = Arena::default();
 218         let root = modules.alloc(ModuleData::default());
 219         DefMap {
 220             _c: Count::new(),
 221             parent: None,
 222             krate,
 223             edition,
 224             extern_prelude: FxHashMap::default(),
 225             prelude: None,
 226             root,
 227             modules,
 228             diagnostics: Vec::new(),
 229         }
 230     }
 231
 232     pub fn add_diagnostics(
 233         &self,
 234         db: &dyn DefDatabase,
 235         module: LocalModuleId,
 236         sink: &mut DiagnosticSink,
 237     ) {
 238         self.diagnostics.iter().for_each(|it| it.add_to(db, module, sink))
 239     }
 240
 241     pub fn modules_for_file(&self, file_id: FileId) -> impl Iterator<Item = LocalModuleId> + '_ {
 242         self.modules
 243             .iter()
 244             .filter(move |(_id, data)| data.origin.file_id() == Some(file_id))
 245             .map(|(id, _data)| id)
 246     }
 247
 248     pub fn modules(&self) -> impl Iterator<Item = (LocalModuleId, &ModuleData)> + '_ {
 249         self.modules.iter()
 250     }
 251
 252     pub fn root(&self) -> LocalModuleId {
 253         self.root
 254     }
 255
 256     pub(crate) fn krate(&self) -> CrateId {
 257         self.krate
 258     }
 259
 260     pub(crate) fn prelude(&self) -> Option<ModuleId> {
 261         self.prelude
 262     }
 263
 264     pub(crate) fn extern_prelude(&self) -> impl Iterator<Item = (&Name, &ModuleDefId)> + '_ {
 265         self.extern_prelude.iter()
 266     }
 267
 268     pub(crate) fn resolve_path(
 269         &self,
 270         db: &dyn DefDatabase,
 271         original_module: LocalModuleId,
 272         path: &ModPath,
 273         shadow: BuiltinShadowMode,
 274     ) -> (PerNs, Option<usize>) {
 275         let res =
 276             self.resolve_path_fp_with_macro(db, ResolveMode::Other, original_module, path, shadow);
 277         (res.resolved_def, res.segment_index)
 278     }
 279
 280     // FIXME: this can use some more human-readable format (ideally, an IR
 281     // even), as this should be a great debugging aid.
 282     pub fn dump(&self) -> String {
 283         let mut buf = String::new();
 284         let mut current_map = self;
 285         while let Some(parent) = &current_map.parent {
 286             go(&mut buf, current_map, "block scope", current_map.root);
 287             current_map = &**parent;
 288         }
 289         go(&mut buf, current_map, "crate", current_map.root);
 290         return buf;
 291
 292         fn go(buf: &mut String, map: &DefMap, path: &str, module: LocalModuleId) {
 293             format_to!(buf, "{}\n", path);
 294
 295             let mut entries: Vec<_> = map.modules[module].scope.resolutions().collect();
 296             entries.sort_by_key(|(name, _)| name.clone());
 297
 298             for (name, def) in entries {
 299                 format_to!(buf, "{}:", name.map_or("_".to_string(), |name| name.to_string()));
 300
 301                 if def.types.is_some() {
 302                     buf.push_str(" t");
 303                 }
 304                 if def.values.is_some() {
 305                     buf.push_str(" v");
 306                 }
 307                 if def.macros.is_some() {
 308                     buf.push_str(" m");
 309                 }
 310                 if def.is_none() {
 311                     buf.push_str(" _");
 312                 }
 313
 314                 buf.push('\n');
 315             }
 316
 317             for (name, child) in map.modules[module].children.iter() {
 318                 let path = format!("{}::{}", path, name);
 319                 buf.push('\n');
 320                 go(buf, map, &path, *child);
 321             }
 322         }
 323     }
 324 }
 325
 326 impl ModuleData {
 327     /// Returns a node which defines this module. That is, a file or a `mod foo {}` with items.
 328     pub fn definition_source(&self, db: &dyn DefDatabase) -> InFile<ModuleSource> {
 329         self.origin.definition_source(db)
 330     }
 331
 332     /// Returns a node which declares this module, either a `mod foo;` or a `mod foo {}`.
 333     /// `None` for the crate root or block.
 334     pub fn declaration_source(&self, db: &dyn DefDatabase) -> Option<InFile<ast::Module>> {
 335         let decl = self.origin.declaration()?;
 336         let value = decl.to_node(db.upcast());
 337         Some(InFile { file_id: decl.file_id, value })
 338     }
 339 }
 340
 341 fn parent_def_map(
 342     db: &dyn DefDatabase,
 343     krate: CrateId,
 344     block: AstId<ast::BlockExpr>,
 345 ) -> Arc<DefMap> {
 346     // FIXME: store this info in the item tree instead of reparsing here
 347     let ast_id_map = db.ast_id_map(block.file_id);
 348     let block_ptr = ast_id_map.get(block.value);
 349     let root = match db.parse_or_expand(block.file_id) {
 350         Some(it) => it,
 351         None => {
 352             return Arc::new(DefMap::empty(krate, Edition::Edition2018));
 353         }
 354     };
 355     let ast = block_ptr.to_node(&root);
 356
 357     for ancestor in ast.syntax().ancestors().skip(1) {
 358         if let Some(block_expr) = ast::BlockExpr::cast(ancestor) {
 359             let ancestor_id = ast_id_map.ast_id(&block_expr);
 360             let ast_id = InFile::new(block.file_id, ancestor_id);
 361             let parent_map = db.block_def_map(krate, ast_id);
 362             return parent_map;
 363         }
 364     }
 365
 366     // No enclosing block scope, so the parent is the crate-level DefMap.
 367     db.crate_def_map(krate)
 368 }
 369
 370 #[derive(Debug, Clone, PartialEq, Eq)]
 371 pub enum ModuleSource {
 372     SourceFile(ast::SourceFile),
 373     Module(ast::Module),
 374     BlockExpr(ast::BlockExpr),
 375 }
 376
 377 mod diagnostics {
 378     use cfg::{CfgExpr, CfgOptions};
 379     use hir_expand::diagnostics::DiagnosticSink;
 380     use hir_expand::hygiene::Hygiene;
 381     use hir_expand::{InFile, MacroCallKind};
 382     use syntax::ast::AttrsOwner;
 383     use syntax::{ast, AstNode, AstPtr, SyntaxKind, SyntaxNodePtr};
 384
 385     use crate::path::ModPath;
 386     use crate::{db::DefDatabase, diagnostics::*, nameres::LocalModuleId, AstId};
 387
 388     #[derive(Debug, PartialEq, Eq)]
 389     enum DiagnosticKind {
 390         UnresolvedModule { declaration: AstId<ast::Module>, candidate: String },
 391
 392         UnresolvedExternCrate { ast: AstId<ast::ExternCrate> },
 393
 394         UnresolvedImport { ast: AstId<ast::Use>, index: usize },
 395
 396         UnconfiguredCode { ast: AstId<ast::Item>, cfg: CfgExpr, opts: CfgOptions },
 397
 398         UnresolvedProcMacro { ast: MacroCallKind },
 399
 400         MacroError { ast: MacroCallKind, message: String },
 401     }
 402
 403     #[derive(Debug, PartialEq, Eq)]
 404     pub(super) struct DefDiagnostic {
 405         in_module: LocalModuleId,
 406         kind: DiagnosticKind,
 407     }
 408
 409     impl DefDiagnostic {
 410         pub(super) fn unresolved_module(
 411             container: LocalModuleId,
 412             declaration: AstId<ast::Module>,
 413             candidate: String,
 414         ) -> Self {
 415             Self {
 416                 in_module: container,
 417                 kind: DiagnosticKind::UnresolvedModule { declaration, candidate },
 418             }
 419         }
 420
 421         pub(super) fn unresolved_extern_crate(
 422             container: LocalModuleId,
 423             declaration: AstId<ast::ExternCrate>,
 424         ) -> Self {
 425             Self {
 426                 in_module: container,
 427                 kind: DiagnosticKind::UnresolvedExternCrate { ast: declaration },
 428             }
 429         }
 430
 431         pub(super) fn unresolved_import(
 432             container: LocalModuleId,
 433             ast: AstId<ast::Use>,
 434             index: usize,
 435         ) -> Self {
 436             Self { in_module: container, kind: DiagnosticKind::UnresolvedImport { ast, index } }
 437         }
 438
 439         pub(super) fn unconfigured_code(
 440             container: LocalModuleId,
 441             ast: AstId<ast::Item>,
 442             cfg: CfgExpr,
 443             opts: CfgOptions,
 444         ) -> Self {
 445             Self { in_module: container, kind: DiagnosticKind::UnconfiguredCode { ast, cfg, opts } }
 446         }
 447
 448         pub(super) fn unresolved_proc_macro(container: LocalModuleId, ast: MacroCallKind) -> Self {
 449             Self { in_module: container, kind: DiagnosticKind::UnresolvedProcMacro { ast } }
 450         }
 451
 452         pub(super) fn macro_error(
 453             container: LocalModuleId,
 454             ast: MacroCallKind,
 455             message: String,
 456         ) -> Self {
 457             Self { in_module: container, kind: DiagnosticKind::MacroError { ast, message } }
 458         }
 459
 460         pub(super) fn add_to(
 461             &self,
 462             db: &dyn DefDatabase,
 463             target_module: LocalModuleId,
 464             sink: &mut DiagnosticSink,
 465         ) {
 466             if self.in_module != target_module {
 467                 return;
 468             }
 469
 470             match &self.kind {
 471                 DiagnosticKind::UnresolvedModule { declaration, candidate } => {
 472                     let decl = declaration.to_node(db.upcast());
 473                     sink.push(UnresolvedModule {
 474                         file: declaration.file_id,
 475                         decl: AstPtr::new(&decl),
 476                         candidate: candidate.clone(),
 477                     })
 478                 }
 479
 480                 DiagnosticKind::UnresolvedExternCrate { ast } => {
 481                     let item = ast.to_node(db.upcast());
 482                     sink.push(UnresolvedExternCrate {
 483                         file: ast.file_id,
 484                         item: AstPtr::new(&item),
 485                     });
 486                 }
 487
 488                 DiagnosticKind::UnresolvedImport { ast, index } => {
 489                     let use_item = ast.to_node(db.upcast());
 490                     let hygiene = Hygiene::new(db.upcast(), ast.file_id);
 491                     let mut cur = 0;
 492                     let mut tree = None;
 493                     ModPath::expand_use_item(
 494                         InFile::new(ast.file_id, use_item),
 495                         &hygiene,
 496                         |_mod_path, use_tree, _is_glob, _alias| {
 497                             if cur == *index {
 498                                 tree = Some(use_tree.clone());
 499                             }
 500
 501                             cur += 1;
 502                         },
 503                     );
 504
 505                     if let Some(tree) = tree {
 506                         sink.push(UnresolvedImport { file: ast.file_id, node: AstPtr::new(&tree) });
 507                     }
 508                 }
 509
 510                 DiagnosticKind::UnconfiguredCode { ast, cfg, opts } => {
 511                     let item = ast.to_node(db.upcast());
 512                     sink.push(InactiveCode {
 513                         file: ast.file_id,
 514                         node: AstPtr::new(&item).into(),
 515                         cfg: cfg.clone(),
 516                         opts: opts.clone(),
 517                     });
 518                 }
 519
 520                 DiagnosticKind::UnresolvedProcMacro { ast } => {
 521                     let mut precise_location = None;
 522                     let (file, ast, name) = match ast {
 523                         MacroCallKind::FnLike(ast) => {
 524                             let node = ast.to_node(db.upcast());
 525                             (ast.file_id, SyntaxNodePtr::from(AstPtr::new(&node)), None)
 526                         }
 527                         MacroCallKind::Attr(ast, name) => {
 528                             let node = ast.to_node(db.upcast());
 529
 530                             // Compute the precise location of the macro name's token in the derive
 531                             // list.
 532                             // FIXME: This does not handle paths to the macro, but neither does the
 533                             // rest of r-a.
 534                             let derive_attrs =
 535                                 node.attrs().filter_map(|attr| match attr.as_simple_call() {
 536                                     Some((name, args)) if name == "derive" => Some(args),
 537                                     _ => None,
 538                                 });
 539                             'outer: for attr in derive_attrs {
 540                                 let tokens =
 541                                     attr.syntax().children_with_tokens().filter_map(|elem| {
 542                                         match elem {
 543                                             syntax::NodeOrToken::Node(_) => None,
 544                                             syntax::NodeOrToken::Token(tok) => Some(tok),
 545                                         }
 546                                     });
 547                                 for token in tokens {
 548                                     if token.kind() == SyntaxKind::IDENT
 549                                         && token.text() == name.as_str()
 550                                     {
 551                                         precise_location = Some(token.text_range());
 552                                         break 'outer;
 553                                     }
 554                                 }
 555                             }
 556
 557                             (
 558                                 ast.file_id,
 559                                 SyntaxNodePtr::from(AstPtr::new(&node)),
 560                                 Some(name.clone()),
 561                             )
 562                         }
 563                     };
 564                     sink.push(UnresolvedProcMacro {
 565                         file,
 566                         node: ast,
 567                         precise_location,
 568                         macro_name: name,
 569                     });
 570                 }
 571
 572                 DiagnosticKind::MacroError { ast, message } => {
 573                     let (file, ast) = match ast {
 574                         MacroCallKind::FnLike(ast) => {
 575                             let node = ast.to_node(db.upcast());
 576                             (ast.file_id, SyntaxNodePtr::from(AstPtr::new(&node)))
 577                         }
 578                         MacroCallKind::Attr(ast, _) => {
 579                             let node = ast.to_node(db.upcast());
 580                             (ast.file_id, SyntaxNodePtr::from(AstPtr::new(&node)))
 581                         }
 582                     };
 583                     sink.push(MacroError { file, node: ast, message: message.clone() });
 584                 }
 585             }
 586         }
 587     }
 588 }