src/tools/rust-analyzer/crates/hir-def/src/item_scope.rs

   1 //! Describes items defined or visible (ie, imported) in a certain scope.
   2 //! This is shared between modules and blocks.
   3
   4 use std::collections::hash_map::Entry;
   5
   6 use base_db::CrateId;
   7 use hir_expand::{name::Name, AstId, MacroCallId};
   8 use itertools::Itertools;
   9 use once_cell::sync::Lazy;
  10 use profile::Count;
  11 use rustc_hash::{FxHashMap, FxHashSet};
  12 use smallvec::{smallvec, SmallVec};
  13 use stdx::format_to;
  14 use syntax::ast;
  15
  16 use crate::{
  17     attr::AttrId, db::DefDatabase, per_ns::PerNs, visibility::Visibility, AdtId, BuiltinType,
  18     ConstId, HasModule, ImplId, LocalModuleId, MacroId, ModuleDefId, ModuleId, TraitId,
  19 };
  20
  21 #[derive(Copy, Clone)]
  22 pub(crate) enum ImportType {
  23     Glob,
  24     Named,
  25 }
  26
  27 #[derive(Debug, Default)]
  28 pub struct PerNsGlobImports {
  29     types: FxHashSet<(LocalModuleId, Name)>,
  30     values: FxHashSet<(LocalModuleId, Name)>,
  31     macros: FxHashSet<(LocalModuleId, Name)>,
  32 }
  33
  34 #[derive(Debug, Default, PartialEq, Eq)]
  35 pub struct ItemScope {
  36     _c: Count<Self>,
  37
  38     /// Defs visible in this scope. This includes `declarations`, but also
  39     /// imports.
  40     types: FxHashMap<Name, (ModuleDefId, Visibility)>,
  41     values: FxHashMap<Name, (ModuleDefId, Visibility)>,
  42     macros: FxHashMap<Name, (MacroId, Visibility)>,
  43     unresolved: FxHashSet<Name>,
  44
  45     /// The defs declared in this scope. Each def has a single scope where it is
  46     /// declared.
  47     declarations: Vec<ModuleDefId>,
  48
  49     impls: Vec<ImplId>,
  50     unnamed_consts: Vec<ConstId>,
  51     /// Traits imported via `use Trait as _;`.
  52     unnamed_trait_imports: FxHashMap<TraitId, Visibility>,
  53     /// Macros visible in current module in legacy textual scope
  54     ///
  55     /// For macros invoked by an unqualified identifier like `bar!()`, `legacy_macros` will be searched in first.
  56     /// If it yields no result, then it turns to module scoped `macros`.
  57     /// It macros with name qualified with a path like `crate::foo::bar!()`, `legacy_macros` will be skipped,
  58     /// and only normal scoped `macros` will be searched in.
  59     ///
  60     /// Note that this automatically inherit macros defined textually before the definition of module itself.
  61     ///
  62     /// Module scoped macros will be inserted into `items` instead of here.
  63     // FIXME: Macro shadowing in one module is not properly handled. Non-item place macros will
  64     // be all resolved to the last one defined if shadowing happens.
  65     legacy_macros: FxHashMap<Name, SmallVec<[MacroId; 1]>>,
  66     /// The derive macro invocations in this scope.
  67     attr_macros: FxHashMap<AstId<ast::Item>, MacroCallId>,
  68     /// The derive macro invocations in this scope, keyed by the owner item over the actual derive attributes
  69     /// paired with the derive macro invocations for the specific attribute.
  70     derive_macros: FxHashMap<AstId<ast::Adt>, SmallVec<[DeriveMacroInvocation; 1]>>,
  71 }
  72
  73 #[derive(Debug, PartialEq, Eq)]
  74 struct DeriveMacroInvocation {
  75     attr_id: AttrId,
  76     attr_call_id: MacroCallId,
  77     derive_call_ids: SmallVec<[Option<MacroCallId>; 1]>,
  78 }
  79
  80 pub(crate) static BUILTIN_SCOPE: Lazy<FxHashMap<Name, PerNs>> = Lazy::new(|| {
  81     BuiltinType::ALL
  82         .iter()
  83         .map(|(name, ty)| (name.clone(), PerNs::types((*ty).into(), Visibility::Public)))
  84         .collect()
  85 });
  86
  87 /// Shadow mode for builtin type which can be shadowed by module.
  88 #[derive(Debug, Copy, Clone, PartialEq, Eq)]
  89 pub(crate) enum BuiltinShadowMode {
  90     /// Prefer user-defined modules (or other types) over builtins.
  91     Module,
  92     /// Prefer builtins over user-defined modules (but not other types).
  93     Other,
  94 }
  95
  96 /// Legacy macros can only be accessed through special methods like `get_legacy_macros`.
  97 /// Other methods will only resolve values, types and module scoped macros only.
  98 impl ItemScope {
  99     pub fn entries<'a>(&'a self) -> impl Iterator<Item = (&'a Name, PerNs)> + 'a {
 100         // FIXME: shadowing
 101         self.types
 102             .keys()
 103             .chain(self.values.keys())
 104             .chain(self.macros.keys())
 105             .chain(self.unresolved.iter())
 106             .sorted()
 107             .unique()
 108             .map(move |name| (name, self.get(name)))
 109     }
 110
 111     pub fn declarations(&self) -> impl Iterator<Item = ModuleDefId> + '_ {
 112         self.declarations.iter().copied()
 113     }
 114
 115     pub fn impls(&self) -> impl Iterator<Item = ImplId> + ExactSizeIterator + '_ {
 116         self.impls.iter().copied()
 117     }
 118
 119     pub fn values(
 120         &self,
 121     ) -> impl Iterator<Item = (ModuleDefId, Visibility)> + ExactSizeIterator + '_ {
 122         self.values.values().copied()
 123     }
 124
 125     pub fn types(
 126         &self,
 127     ) -> impl Iterator<Item = (ModuleDefId, Visibility)> + ExactSizeIterator + '_ {
 128         self.types.values().copied()
 129     }
 130
 131     pub fn unnamed_consts(&self) -> impl Iterator<Item = ConstId> + '_ {
 132         self.unnamed_consts.iter().copied()
 133     }
 134
 135     /// Iterate over all module scoped macros
 136     pub(crate) fn macros(&self) -> impl Iterator<Item = (&Name, MacroId)> + '_ {
 137         self.entries().filter_map(|(name, def)| def.take_macros().map(|macro_| (name, macro_)))
 138     }
 139
 140     /// Iterate over all legacy textual scoped macros visible at the end of the module
 141     pub fn legacy_macros(&self) -> impl Iterator<Item = (&Name, &[MacroId])> + '_ {
 142         self.legacy_macros.iter().map(|(name, def)| (name, &**def))
 143     }
 144
 145     /// Get a name from current module scope, legacy macros are not included
 146     pub(crate) fn get(&self, name: &Name) -> PerNs {
 147         PerNs {
 148             types: self.types.get(name).copied(),
 149             values: self.values.get(name).copied(),
 150             macros: self.macros.get(name).copied(),
 151         }
 152     }
 153
 154     pub(crate) fn type_(&self, name: &Name) -> Option<(ModuleDefId, Visibility)> {
 155         self.types.get(name).copied()
 156     }
 157
 158     /// XXX: this is O(N) rather than O(1), try to not introduce new usages.
 159     pub(crate) fn name_of(&self, item: ItemInNs) -> Option<(&Name, Visibility)> {
 160         let (def, mut iter) = match item {
 161             ItemInNs::Macros(def) => {
 162                 return self
 163                     .macros
 164                     .iter()
 165                     .find_map(|(name, &(other_def, vis))| (other_def == def).then(|| (name, vis)));
 166             }
 167             ItemInNs::Types(def) => (def, self.types.iter()),
 168             ItemInNs::Values(def) => (def, self.values.iter()),
 169         };
 170         iter.find_map(|(name, &(other_def, vis))| (other_def == def).then(|| (name, vis)))
 171     }
 172
 173     pub(crate) fn traits<'a>(&'a self) -> impl Iterator<Item = TraitId> + 'a {
 174         self.types
 175             .values()
 176             .filter_map(|&(def, _)| match def {
 177                 ModuleDefId::TraitId(t) => Some(t),
 178                 _ => None,
 179             })
 180             .chain(self.unnamed_trait_imports.keys().copied())
 181     }
 182
 183     pub(crate) fn declare(&mut self, def: ModuleDefId) {
 184         self.declarations.push(def)
 185     }
 186
 187     pub(crate) fn get_legacy_macro(&self, name: &Name) -> Option<&[MacroId]> {
 188         self.legacy_macros.get(name).map(|it| &**it)
 189     }
 190
 191     pub(crate) fn define_impl(&mut self, imp: ImplId) {
 192         self.impls.push(imp)
 193     }
 194
 195     pub(crate) fn define_unnamed_const(&mut self, konst: ConstId) {
 196         self.unnamed_consts.push(konst);
 197     }
 198
 199     pub(crate) fn define_legacy_macro(&mut self, name: Name, mac: MacroId) {
 200         self.legacy_macros.entry(name).or_default().push(mac);
 201     }
 202
 203     pub(crate) fn add_attr_macro_invoc(&mut self, item: AstId<ast::Item>, call: MacroCallId) {
 204         self.attr_macros.insert(item, call);
 205     }
 206
 207     pub(crate) fn attr_macro_invocs(
 208         &self,
 209     ) -> impl Iterator<Item = (AstId<ast::Item>, MacroCallId)> + '_ {
 210         self.attr_macros.iter().map(|(k, v)| (*k, *v))
 211     }
 212
 213     pub(crate) fn set_derive_macro_invoc(
 214         &mut self,
 215         adt: AstId<ast::Adt>,
 216         call: MacroCallId,
 217         id: AttrId,
 218         idx: usize,
 219     ) {
 220         if let Some(derives) = self.derive_macros.get_mut(&adt) {
 221             if let Some(DeriveMacroInvocation { derive_call_ids, .. }) =
 222                 derives.iter_mut().find(|&&mut DeriveMacroInvocation { attr_id, .. }| id == attr_id)
 223             {
 224                 derive_call_ids[idx] = Some(call);
 225             }
 226         }
 227     }
 228
 229     /// We are required to set this up front as derive invocation recording happens out of order
 230     /// due to the fixed pointer iteration loop being able to record some derives later than others
 231     /// independent of their indices.
 232     pub(crate) fn init_derive_attribute(
 233         &mut self,
 234         adt: AstId<ast::Adt>,
 235         attr_id: AttrId,
 236         attr_call_id: MacroCallId,
 237         len: usize,
 238     ) {
 239         self.derive_macros.entry(adt).or_default().push(DeriveMacroInvocation {
 240             attr_id,
 241             attr_call_id,
 242             derive_call_ids: smallvec![None; len],
 243         });
 244     }
 245
 246     pub(crate) fn derive_macro_invocs(
 247         &self,
 248     ) -> impl Iterator<
 249         Item = (
 250             AstId<ast::Adt>,
 251             impl Iterator<Item = (AttrId, MacroCallId, &[Option<MacroCallId>])>,
 252         ),
 253     > + '_ {
 254         self.derive_macros.iter().map(|(k, v)| {
 255             (
 256                 *k,
 257                 v.iter().map(|DeriveMacroInvocation { attr_id, attr_call_id, derive_call_ids }| {
 258                     (*attr_id, *attr_call_id, &**derive_call_ids)
 259                 }),
 260             )
 261         })
 262     }
 263
 264     pub(crate) fn unnamed_trait_vis(&self, tr: TraitId) -> Option<Visibility> {
 265         self.unnamed_trait_imports.get(&tr).copied()
 266     }
 267
 268     pub(crate) fn push_unnamed_trait(&mut self, tr: TraitId, vis: Visibility) {
 269         self.unnamed_trait_imports.insert(tr, vis);
 270     }
 271
 272     pub(crate) fn push_res_with_import(
 273         &mut self,
 274         glob_imports: &mut PerNsGlobImports,
 275         lookup: (LocalModuleId, Name),
 276         def: PerNs,
 277         def_import_type: ImportType,
 278     ) -> bool {
 279         let mut changed = false;
 280
 281         macro_rules! check_changed {
 282             (
 283                 $changed:ident,
 284                 ( $this:ident / $def:ident ) . $field:ident,
 285                 $glob_imports:ident [ $lookup:ident ],
 286                 $def_import_type:ident
 287             ) => {{
 288                 if let Some(fld) = $def.$field {
 289                     let existing = $this.$field.entry($lookup.1.clone());
 290                     match existing {
 291                         Entry::Vacant(entry) => {
 292                             match $def_import_type {
 293                                 ImportType::Glob => {
 294                                     $glob_imports.$field.insert($lookup.clone());
 295                                 }
 296                                 ImportType::Named => {
 297                                     $glob_imports.$field.remove(&$lookup);
 298                                 }
 299                             }
 300
 301                             entry.insert(fld);
 302                             $changed = true;
 303                         }
 304                         Entry::Occupied(mut entry)
 305                             if $glob_imports.$field.contains(&$lookup)
 306                                 && matches!($def_import_type, ImportType::Named) =>
 307                         {
 308                             cov_mark::hit!(import_shadowed);
 309                             $glob_imports.$field.remove(&$lookup);
 310                             entry.insert(fld);
 311                             $changed = true;
 312                         }
 313                         _ => {}
 314                     }
 315                 }
 316             }};
 317         }
 318
 319         check_changed!(changed, (self / def).types, glob_imports[lookup], def_import_type);
 320         check_changed!(changed, (self / def).values, glob_imports[lookup], def_import_type);
 321         check_changed!(changed, (self / def).macros, glob_imports[lookup], def_import_type);
 322
 323         if def.is_none() && self.unresolved.insert(lookup.1) {
 324             changed = true;
 325         }
 326
 327         changed
 328     }
 329
 330     pub(crate) fn resolutions<'a>(&'a self) -> impl Iterator<Item = (Option<Name>, PerNs)> + 'a {
 331         self.entries().map(|(name, res)| (Some(name.clone()), res)).chain(
 332             self.unnamed_trait_imports
 333                 .iter()
 334                 .map(|(tr, vis)| (None, PerNs::types(ModuleDefId::TraitId(*tr), *vis))),
 335         )
 336     }
 337
 338     pub(crate) fn collect_legacy_macros(&self) -> FxHashMap<Name, SmallVec<[MacroId; 1]>> {
 339         self.legacy_macros.clone()
 340     }
 341
 342     /// Marks everything that is not a procedural macro as private to `this_module`.
 343     pub(crate) fn censor_non_proc_macros(&mut self, this_module: ModuleId) {
 344         self.types
 345             .values_mut()
 346             .chain(self.values.values_mut())
 347             .map(|(_, v)| v)
 348             .chain(self.unnamed_trait_imports.values_mut())
 349             .for_each(|vis| *vis = Visibility::Module(this_module));
 350
 351         for (mac, vis) in self.macros.values_mut() {
 352             if let MacroId::ProcMacroId(_) = mac {
 353                 // FIXME: Technically this is insufficient since reexports of proc macros are also
 354                 // forbidden. Practically nobody does that.
 355                 continue;
 356             }
 357
 358             *vis = Visibility::Module(this_module);
 359         }
 360     }
 361
 362     pub(crate) fn dump(&self, buf: &mut String) {
 363         let mut entries: Vec<_> = self.resolutions().collect();
 364         entries.sort_by_key(|(name, _)| name.clone());
 365
 366         for (name, def) in entries {
 367             format_to!(buf, "{}:", name.map_or("_".to_string(), |name| name.to_string()));
 368
 369             if def.types.is_some() {
 370                 buf.push_str(" t");
 371             }
 372             if def.values.is_some() {
 373                 buf.push_str(" v");
 374             }
 375             if def.macros.is_some() {
 376                 buf.push_str(" m");
 377             }
 378             if def.is_none() {
 379                 buf.push_str(" _");
 380             }
 381
 382             buf.push('\n');
 383         }
 384     }
 385
 386     pub(crate) fn shrink_to_fit(&mut self) {
 387         // Exhaustive match to require handling new fields.
 388         let Self {
 389             _c: _,
 390             types,
 391             values,
 392             macros,
 393             unresolved,
 394             declarations,
 395             impls,
 396             unnamed_consts,
 397             unnamed_trait_imports,
 398             legacy_macros,
 399             attr_macros,
 400             derive_macros,
 401         } = self;
 402         types.shrink_to_fit();
 403         values.shrink_to_fit();
 404         macros.shrink_to_fit();
 405         unresolved.shrink_to_fit();
 406         declarations.shrink_to_fit();
 407         impls.shrink_to_fit();
 408         unnamed_consts.shrink_to_fit();
 409         unnamed_trait_imports.shrink_to_fit();
 410         legacy_macros.shrink_to_fit();
 411         attr_macros.shrink_to_fit();
 412         derive_macros.shrink_to_fit();
 413     }
 414 }
 415
 416 impl PerNs {
 417     pub(crate) fn from_def(def: ModuleDefId, v: Visibility, has_constructor: bool) -> PerNs {
 418         match def {
 419             ModuleDefId::ModuleId(_) => PerNs::types(def, v),
 420             ModuleDefId::FunctionId(_) => PerNs::values(def, v),
 421             ModuleDefId::AdtId(adt) => match adt {
 422                 AdtId::UnionId(_) => PerNs::types(def, v),
 423                 AdtId::EnumId(_) => PerNs::types(def, v),
 424                 AdtId::StructId(_) => {
 425                     if has_constructor {
 426                         PerNs::both(def, def, v)
 427                     } else {
 428                         PerNs::types(def, v)
 429                     }
 430                 }
 431             },
 432             ModuleDefId::EnumVariantId(_) => PerNs::both(def, def, v),
 433             ModuleDefId::ConstId(_) | ModuleDefId::StaticId(_) => PerNs::values(def, v),
 434             ModuleDefId::TraitId(_) => PerNs::types(def, v),
 435             ModuleDefId::TypeAliasId(_) => PerNs::types(def, v),
 436             ModuleDefId::BuiltinType(_) => PerNs::types(def, v),
 437             ModuleDefId::MacroId(mac) => PerNs::macros(mac, v),
 438         }
 439     }
 440 }
 441
 442 #[derive(Clone, Copy, PartialEq, Eq, Debug, Hash)]
 443 pub enum ItemInNs {
 444     Types(ModuleDefId),
 445     Values(ModuleDefId),
 446     Macros(MacroId),
 447 }
 448
 449 impl ItemInNs {
 450     pub fn as_module_def_id(self) -> Option<ModuleDefId> {
 451         match self {
 452             ItemInNs::Types(id) | ItemInNs::Values(id) => Some(id),
 453             ItemInNs::Macros(_) => None,
 454         }
 455     }
 456
 457     /// Returns the crate defining this item (or `None` if `self` is built-in).
 458     pub fn krate(&self, db: &dyn DefDatabase) -> Option<CrateId> {
 459         match self {
 460             ItemInNs::Types(did) | ItemInNs::Values(did) => did.module(db).map(|m| m.krate),
 461             ItemInNs::Macros(id) => Some(id.module(db).krate),
 462         }
 463     }
 464 }