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

   1 //! Name resolution façade.
   2 use std::{hash::BuildHasherDefault, sync::Arc};
   3
   4 use base_db::CrateId;
   5 use hir_expand::name::{name, Name};
   6 use indexmap::IndexMap;
   7 use rustc_hash::FxHashSet;
   8 use smallvec::{smallvec, SmallVec};
   9
  10 use crate::{
  11     body::scope::{ExprScopes, ScopeId},
  12     builtin_type::BuiltinType,
  13     db::DefDatabase,
  14     expr::{ExprId, LabelId, PatId},
  15     generics::{GenericParams, TypeOrConstParamData},
  16     intern::Interned,
  17     item_scope::{BuiltinShadowMode, BUILTIN_SCOPE},
  18     nameres::DefMap,
  19     path::{ModPath, PathKind},
  20     per_ns::PerNs,
  21     visibility::{RawVisibility, Visibility},
  22     AdtId, AssocItemId, ConstId, ConstParamId, DefWithBodyId, EnumId, EnumVariantId, ExternBlockId,
  23     FunctionId, GenericDefId, GenericParamId, HasModule, ImplId, ItemContainerId, LifetimeParamId,
  24     LocalModuleId, Lookup, Macro2Id, MacroId, MacroRulesId, ModuleDefId, ModuleId, ProcMacroId,
  25     StaticId, StructId, TraitId, TypeAliasId, TypeOrConstParamId, TypeParamId, VariantId,
  26 };
  27
  28 #[derive(Debug, Clone)]
  29 pub struct Resolver {
  30     /// The stack of scopes, where the inner-most scope is the last item.
  31     ///
  32     /// When using, you generally want to process the scopes in reverse order,
  33     /// there's `scopes` *method* for that.
  34     scopes: Vec<Scope>,
  35     module_scope: ModuleItemMap,
  36 }
  37
  38 #[derive(Debug, Clone)]
  39 struct ModuleItemMap {
  40     def_map: Arc<DefMap>,
  41     module_id: LocalModuleId,
  42 }
  43
  44 #[derive(Debug, Clone)]
  45 struct ExprScope {
  46     owner: DefWithBodyId,
  47     expr_scopes: Arc<ExprScopes>,
  48     scope_id: ScopeId,
  49 }
  50
  51 #[derive(Debug, Clone)]
  52 enum Scope {
  53     /// All the items and imported names of a module
  54     BlockScope(ModuleItemMap),
  55     /// Brings the generic parameters of an item into scope
  56     GenericParams { def: GenericDefId, params: Interned<GenericParams> },
  57     /// Brings `Self` in `impl` block into scope
  58     ImplDefScope(ImplId),
  59     /// Brings `Self` in enum, struct and union definitions into scope
  60     AdtScope(AdtId),
  61     /// Local bindings
  62     ExprScope(ExprScope),
  63 }
  64
  65 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
  66 pub enum TypeNs {
  67     SelfType(ImplId),
  68     GenericParam(TypeParamId),
  69     AdtId(AdtId),
  70     AdtSelfType(AdtId),
  71     // Yup, enum variants are added to the types ns, but any usage of variant as
  72     // type is an error.
  73     EnumVariantId(EnumVariantId),
  74     TypeAliasId(TypeAliasId),
  75     BuiltinType(BuiltinType),
  76     TraitId(TraitId),
  77     // Module belong to type ns, but the resolver is used when all module paths
  78     // are fully resolved.
  79     // ModuleId(ModuleId)
  80 }
  81
  82 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
  83 pub enum ResolveValueResult {
  84     ValueNs(ValueNs),
  85     Partial(TypeNs, usize),
  86 }
  87
  88 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
  89 pub enum ValueNs {
  90     ImplSelf(ImplId),
  91     LocalBinding(PatId),
  92     FunctionId(FunctionId),
  93     ConstId(ConstId),
  94     StaticId(StaticId),
  95     StructId(StructId),
  96     EnumVariantId(EnumVariantId),
  97     GenericParam(ConstParamId),
  98 }
  99
 100 impl Resolver {
 101     /// Resolve known trait from std, like `std::futures::Future`
 102     pub fn resolve_known_trait(&self, db: &dyn DefDatabase, path: &ModPath) -> Option<TraitId> {
 103         let res = self.resolve_module_path(db, path, BuiltinShadowMode::Other).take_types()?;
 104         match res {
 105             ModuleDefId::TraitId(it) => Some(it),
 106             _ => None,
 107         }
 108     }
 109
 110     /// Resolve known struct from std, like `std::boxed::Box`
 111     pub fn resolve_known_struct(&self, db: &dyn DefDatabase, path: &ModPath) -> Option<StructId> {
 112         let res = self.resolve_module_path(db, path, BuiltinShadowMode::Other).take_types()?;
 113         match res {
 114             ModuleDefId::AdtId(AdtId::StructId(it)) => Some(it),
 115             _ => None,
 116         }
 117     }
 118
 119     /// Resolve known enum from std, like `std::result::Result`
 120     pub fn resolve_known_enum(&self, db: &dyn DefDatabase, path: &ModPath) -> Option<EnumId> {
 121         let res = self.resolve_module_path(db, path, BuiltinShadowMode::Other).take_types()?;
 122         match res {
 123             ModuleDefId::AdtId(AdtId::EnumId(it)) => Some(it),
 124             _ => None,
 125         }
 126     }
 127
 128     pub fn resolve_module_path_in_items(&self, db: &dyn DefDatabase, path: &ModPath) -> PerNs {
 129         self.resolve_module_path(db, path, BuiltinShadowMode::Module)
 130     }
 131
 132     // FIXME: This shouldn't exist
 133     pub fn resolve_module_path_in_trait_assoc_items(
 134         &self,
 135         db: &dyn DefDatabase,
 136         path: &ModPath,
 137     ) -> Option<PerNs> {
 138         let (item_map, module) = self.item_scope();
 139         let (module_res, idx) = item_map.resolve_path(db, module, path, BuiltinShadowMode::Module);
 140         match module_res.take_types()? {
 141             ModuleDefId::TraitId(it) => {
 142                 let idx = idx?;
 143                 let unresolved = &path.segments()[idx..];
 144                 let assoc = match unresolved {
 145                     [it] => it,
 146                     _ => return None,
 147                 };
 148                 let &(_, assoc) = db.trait_data(it).items.iter().find(|(n, _)| n == assoc)?;
 149                 Some(match assoc {
 150                     AssocItemId::FunctionId(it) => PerNs::values(it.into(), Visibility::Public),
 151                     AssocItemId::ConstId(it) => PerNs::values(it.into(), Visibility::Public),
 152                     AssocItemId::TypeAliasId(it) => PerNs::types(it.into(), Visibility::Public),
 153                 })
 154             }
 155             _ => None,
 156         }
 157     }
 158
 159     pub fn resolve_path_in_type_ns(
 160         &self,
 161         db: &dyn DefDatabase,
 162         path: &ModPath,
 163     ) -> Option<(TypeNs, Option<usize>)> {
 164         let first_name = path.segments().first()?;
 165         let skip_to_mod = path.kind != PathKind::Plain;
 166         if skip_to_mod {
 167             return self.module_scope.resolve_path_in_type_ns(db, path);
 168         }
 169
 170         let remaining_idx = || if path.segments().len() == 1 { None } else { Some(1) };
 171
 172         for scope in self.scopes() {
 173             match scope {
 174                 Scope::ExprScope(_) => continue,
 175                 Scope::GenericParams { params, def } => {
 176                     if let Some(id) = params.find_type_by_name(first_name, *def) {
 177                         return Some((TypeNs::GenericParam(id), remaining_idx()));
 178                     }
 179                 }
 180                 &Scope::ImplDefScope(impl_) => {
 181                     if first_name == &name![Self] {
 182                         return Some((TypeNs::SelfType(impl_), remaining_idx()));
 183                     }
 184                 }
 185                 &Scope::AdtScope(adt) => {
 186                     if first_name == &name![Self] {
 187                         return Some((TypeNs::AdtSelfType(adt), remaining_idx()));
 188                     }
 189                 }
 190                 Scope::BlockScope(m) => {
 191                     if let Some(res) = m.resolve_path_in_type_ns(db, path) {
 192                         return Some(res);
 193                     }
 194                 }
 195             }
 196         }
 197         self.module_scope.resolve_path_in_type_ns(db, path)
 198     }
 199
 200     pub fn resolve_path_in_type_ns_fully(
 201         &self,
 202         db: &dyn DefDatabase,
 203         path: &ModPath,
 204     ) -> Option<TypeNs> {
 205         let (res, unresolved) = self.resolve_path_in_type_ns(db, path)?;
 206         if unresolved.is_some() {
 207             return None;
 208         }
 209         Some(res)
 210     }
 211
 212     pub fn resolve_visibility(
 213         &self,
 214         db: &dyn DefDatabase,
 215         visibility: &RawVisibility,
 216     ) -> Option<Visibility> {
 217         match visibility {
 218             RawVisibility::Module(_) => {
 219                 let (item_map, module) = self.item_scope();
 220                 item_map.resolve_visibility(db, module, visibility)
 221             }
 222             RawVisibility::Public => Some(Visibility::Public),
 223         }
 224     }
 225
 226     pub fn resolve_path_in_value_ns(
 227         &self,
 228         db: &dyn DefDatabase,
 229         path: &ModPath,
 230     ) -> Option<ResolveValueResult> {
 231         let n_segments = path.segments().len();
 232         let tmp = name![self];
 233         let first_name = if path.is_self() { &tmp } else { path.segments().first()? };
 234         let skip_to_mod = path.kind != PathKind::Plain && !path.is_self();
 235         if skip_to_mod {
 236             return self.module_scope.resolve_path_in_value_ns(db, path);
 237         }
 238
 239         for scope in self.scopes() {
 240             match scope {
 241                 Scope::ExprScope(_) if n_segments > 1 => continue,
 242                 Scope::ExprScope(scope) => {
 243                     let entry = scope
 244                         .expr_scopes
 245                         .entries(scope.scope_id)
 246                         .iter()
 247                         .find(|entry| entry.name() == first_name);
 248
 249                     if let Some(e) = entry {
 250                         return Some(ResolveValueResult::ValueNs(ValueNs::LocalBinding(e.pat())));
 251                     }
 252                 }
 253                 Scope::GenericParams { params, def } if n_segments > 1 => {
 254                     if let Some(id) = params.find_type_by_name(first_name, *def) {
 255                         let ty = TypeNs::GenericParam(id);
 256                         return Some(ResolveValueResult::Partial(ty, 1));
 257                     }
 258                 }
 259                 Scope::GenericParams { .. } if n_segments != 1 => continue,
 260                 Scope::GenericParams { params, def } => {
 261                     if let Some(id) = params.find_const_by_name(first_name, *def) {
 262                         let val = ValueNs::GenericParam(id);
 263                         return Some(ResolveValueResult::ValueNs(val));
 264                     }
 265                 }
 266
 267                 &Scope::ImplDefScope(impl_) => {
 268                     if first_name == &name![Self] {
 269                         return Some(if n_segments > 1 {
 270                             ResolveValueResult::Partial(TypeNs::SelfType(impl_), 1)
 271                         } else {
 272                             ResolveValueResult::ValueNs(ValueNs::ImplSelf(impl_))
 273                         });
 274                     }
 275                 }
 276                 // bare `Self` doesn't work in the value namespace in a struct/enum definition
 277                 Scope::AdtScope(_) if n_segments == 1 => continue,
 278                 Scope::AdtScope(adt) => {
 279                     if first_name == &name![Self] {
 280                         let ty = TypeNs::AdtSelfType(*adt);
 281                         return Some(ResolveValueResult::Partial(ty, 1));
 282                     }
 283                 }
 284
 285                 Scope::BlockScope(m) => {
 286                     if let Some(def) = m.resolve_path_in_value_ns(db, path) {
 287                         return Some(def);
 288                     }
 289                 }
 290             }
 291         }
 292
 293         if let res @ Some(_) = self.module_scope.resolve_path_in_value_ns(db, path) {
 294             return res;
 295         }
 296
 297         // If a path of the shape `u16::from_le_bytes` failed to resolve at all, then we fall back
 298         // to resolving to the primitive type, to allow this to still work in the presence of
 299         // `use core::u16;`.
 300         if path.kind == PathKind::Plain && path.segments().len() > 1 {
 301             if let Some(builtin) = BuiltinType::by_name(&path.segments()[0]) {
 302                 return Some(ResolveValueResult::Partial(TypeNs::BuiltinType(builtin), 1));
 303             }
 304         }
 305
 306         None
 307     }
 308
 309     pub fn resolve_path_in_value_ns_fully(
 310         &self,
 311         db: &dyn DefDatabase,
 312         path: &ModPath,
 313     ) -> Option<ValueNs> {
 314         match self.resolve_path_in_value_ns(db, path)? {
 315             ResolveValueResult::ValueNs(it) => Some(it),
 316             ResolveValueResult::Partial(..) => None,
 317         }
 318     }
 319
 320     pub fn resolve_path_as_macro(&self, db: &dyn DefDatabase, path: &ModPath) -> Option<MacroId> {
 321         let (item_map, module) = self.item_scope();
 322         item_map.resolve_path(db, module, path, BuiltinShadowMode::Other).0.take_macros()
 323     }
 324
 325     /// Returns a set of names available in the current scope.
 326     ///
 327     /// Note that this is a somewhat fuzzy concept -- internally, the compiler
 328     /// doesn't necessary follow a strict scoping discipline. Rather, it just
 329     /// tells for each ident what it resolves to.
 330     ///
 331     /// A good example is something like `str::from_utf8`. From scopes point of
 332     /// view, this code is erroneous -- both `str` module and `str` type occupy
 333     /// the same type namespace.
 334     ///
 335     /// We don't try to model that super-correctly -- this functionality is
 336     /// primarily exposed for completions.
 337     ///
 338     /// Note that in Rust one name can be bound to several items:
 339     ///
 340     /// ```
 341     /// macro_rules! t { () => (()) }
 342     /// type t = t!();
 343     /// const t: t = t!()
 344     /// ```
 345     ///
 346     /// That's why we return a multimap.
 347     ///
 348     /// The shadowing is accounted for: in
 349     ///
 350     /// ```
 351     /// let x = 92;
 352     /// {
 353     ///     let x = 92;
 354     ///     $0
 355     /// }
 356     /// ```
 357     ///
 358     /// there will be only one entry for `x` in the result.
 359     ///
 360     /// The result is ordered *roughly* from the innermost scope to the
 361     /// outermost: when the name is introduced in two namespaces in two scopes,
 362     /// we use the position of the first scope.
 363     pub fn names_in_scope(
 364         &self,
 365         db: &dyn DefDatabase,
 366     ) -> FxIndexMap<Name, SmallVec<[ScopeDef; 1]>> {
 367         let mut res = ScopeNames::default();
 368         for scope in self.scopes() {
 369             scope.process_names(&mut res, db);
 370         }
 371         let ModuleItemMap { ref def_map, module_id } = self.module_scope;
 372         // FIXME: should we provide `self` here?
 373         // f(
 374         //     Name::self_param(),
 375         //     PerNs::types(Resolution::Def {
 376         //         def: m.module.into(),
 377         //     }),
 378         // );
 379         def_map[module_id].scope.entries().for_each(|(name, def)| {
 380             res.add_per_ns(name, def);
 381         });
 382         def_map[module_id].scope.legacy_macros().for_each(|(name, macs)| {
 383             macs.iter().for_each(|&mac| {
 384                 res.add(name, ScopeDef::ModuleDef(ModuleDefId::MacroId(MacroId::from(mac))));
 385             })
 386         });
 387         def_map.extern_prelude().for_each(|(name, &def)| {
 388             res.add(name, ScopeDef::ModuleDef(ModuleDefId::ModuleId(def)));
 389         });
 390         BUILTIN_SCOPE.iter().for_each(|(name, &def)| {
 391             res.add_per_ns(name, def);
 392         });
 393         if let Some(prelude) = def_map.prelude() {
 394             let prelude_def_map = prelude.def_map(db);
 395             for (name, def) in prelude_def_map[prelude.local_id].scope.entries() {
 396                 res.add_per_ns(name, def)
 397             }
 398         }
 399         res.map
 400     }
 401
 402     pub fn traits_in_scope(&self, db: &dyn DefDatabase) -> FxHashSet<TraitId> {
 403         let mut traits = FxHashSet::default();
 404
 405         for scope in self.scopes() {
 406             match scope {
 407                 Scope::BlockScope(m) => traits.extend(m.def_map[m.module_id].scope.traits()),
 408                 &Scope::ImplDefScope(impl_) => {
 409                     if let Some(target_trait) = &db.impl_data(impl_).target_trait {
 410                         if let Some(TypeNs::TraitId(trait_)) =
 411                             self.resolve_path_in_type_ns_fully(db, target_trait.path.mod_path())
 412                         {
 413                             traits.insert(trait_);
 414                         }
 415                     }
 416                 }
 417                 _ => (),
 418             }
 419         }
 420
 421         // Fill in the prelude traits
 422         if let Some(prelude) = self.module_scope.def_map.prelude() {
 423             let prelude_def_map = prelude.def_map(db);
 424             traits.extend(prelude_def_map[prelude.local_id].scope.traits());
 425         }
 426         // Fill in module visible traits
 427         traits.extend(self.module_scope.def_map[self.module_scope.module_id].scope.traits());
 428         traits
 429     }
 430
 431     pub fn module(&self) -> ModuleId {
 432         let (def_map, local_id) = self.item_scope();
 433         def_map.module_id(local_id)
 434     }
 435
 436     pub fn krate(&self) -> CrateId {
 437         self.module_scope.def_map.krate()
 438     }
 439
 440     pub fn def_map(&self) -> &DefMap {
 441         self.item_scope().0
 442     }
 443
 444     pub fn where_predicates_in_scope(
 445         &self,
 446     ) -> impl Iterator<Item = &crate::generics::WherePredicate> {
 447         self.scopes()
 448             .filter_map(|scope| match scope {
 449                 Scope::GenericParams { params, .. } => Some(params),
 450                 _ => None,
 451             })
 452             .flat_map(|params| params.where_predicates.iter())
 453     }
 454
 455     pub fn generic_def(&self) -> Option<GenericDefId> {
 456         self.scopes().find_map(|scope| match scope {
 457             Scope::GenericParams { def, .. } => Some(*def),
 458             _ => None,
 459         })
 460     }
 461
 462     pub fn body_owner(&self) -> Option<DefWithBodyId> {
 463         self.scopes().find_map(|scope| match scope {
 464             Scope::ExprScope(it) => Some(it.owner),
 465             _ => None,
 466         })
 467     }
 468 }
 469
 470 impl Resolver {
 471     fn scopes(&self) -> impl Iterator<Item = &Scope> {
 472         self.scopes.iter().rev()
 473     }
 474
 475     fn resolve_module_path(
 476         &self,
 477         db: &dyn DefDatabase,
 478         path: &ModPath,
 479         shadow: BuiltinShadowMode,
 480     ) -> PerNs {
 481         let (item_map, module) = self.item_scope();
 482         let (module_res, segment_index) = item_map.resolve_path(db, module, path, shadow);
 483         if segment_index.is_some() {
 484             return PerNs::none();
 485         }
 486         module_res
 487     }
 488
 489     /// The innermost block scope that contains items or the module scope that contains this resolver.
 490     fn item_scope(&self) -> (&DefMap, LocalModuleId) {
 491         self.scopes()
 492             .find_map(|scope| match scope {
 493                 Scope::BlockScope(m) => Some((&*m.def_map, m.module_id)),
 494                 _ => None,
 495             })
 496             .unwrap_or((&self.module_scope.def_map, self.module_scope.module_id))
 497     }
 498 }
 499
 500 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
 501 pub enum ScopeDef {
 502     ModuleDef(ModuleDefId),
 503     Unknown,
 504     ImplSelfType(ImplId),
 505     AdtSelfType(AdtId),
 506     GenericParam(GenericParamId),
 507     Local(PatId),
 508     Label(LabelId),
 509 }
 510
 511 impl Scope {
 512     fn process_names(&self, acc: &mut ScopeNames, db: &dyn DefDatabase) {
 513         match self {
 514             Scope::BlockScope(m) => {
 515                 m.def_map[m.module_id].scope.entries().for_each(|(name, def)| {
 516                     acc.add_per_ns(name, def);
 517                 });
 518                 m.def_map[m.module_id].scope.legacy_macros().for_each(|(name, macs)| {
 519                     macs.iter().for_each(|&mac| {
 520                         acc.add(
 521                             name,
 522                             ScopeDef::ModuleDef(ModuleDefId::MacroId(MacroId::from(mac))),
 523                         );
 524                     })
 525                 });
 526             }
 527             Scope::GenericParams { params, def: parent } => {
 528                 let parent = *parent;
 529                 for (local_id, param) in params.type_or_consts.iter() {
 530                     if let Some(name) = &param.name() {
 531                         let id = TypeOrConstParamId { parent, local_id };
 532                         let data = &db.generic_params(parent).type_or_consts[local_id];
 533                         acc.add(
 534                             name,
 535                             ScopeDef::GenericParam(match data {
 536                                 TypeOrConstParamData::TypeParamData(_) => {
 537                                     GenericParamId::TypeParamId(TypeParamId::from_unchecked(id))
 538                                 }
 539                                 TypeOrConstParamData::ConstParamData(_) => {
 540                                     GenericParamId::ConstParamId(ConstParamId::from_unchecked(id))
 541                                 }
 542                             }),
 543                         );
 544                     }
 545                 }
 546                 for (local_id, param) in params.lifetimes.iter() {
 547                     let id = LifetimeParamId { parent, local_id };
 548                     acc.add(&param.name, ScopeDef::GenericParam(id.into()))
 549                 }
 550             }
 551             Scope::ImplDefScope(i) => {
 552                 acc.add(&name![Self], ScopeDef::ImplSelfType(*i));
 553             }
 554             Scope::AdtScope(i) => {
 555                 acc.add(&name![Self], ScopeDef::AdtSelfType(*i));
 556             }
 557             Scope::ExprScope(scope) => {
 558                 if let Some((label, name)) = scope.expr_scopes.label(scope.scope_id) {
 559                     acc.add(&name, ScopeDef::Label(label))
 560                 }
 561                 scope.expr_scopes.entries(scope.scope_id).iter().for_each(|e| {
 562                     acc.add_local(e.name(), e.pat());
 563                 });
 564             }
 565         }
 566     }
 567 }
 568
 569 // needs arbitrary_self_types to be a method... or maybe move to the def?
 570 pub fn resolver_for_expr(db: &dyn DefDatabase, owner: DefWithBodyId, expr_id: ExprId) -> Resolver {
 571     let scopes = db.expr_scopes(owner);
 572     resolver_for_scope(db, owner, scopes.scope_for(expr_id))
 573 }
 574
 575 pub fn resolver_for_scope(
 576     db: &dyn DefDatabase,
 577     owner: DefWithBodyId,
 578     scope_id: Option<ScopeId>,
 579 ) -> Resolver {
 580     let mut r = owner.resolver(db);
 581     let scopes = db.expr_scopes(owner);
 582     let scope_chain = scopes.scope_chain(scope_id).collect::<Vec<_>>();
 583     r.scopes.reserve(scope_chain.len());
 584
 585     for scope in scope_chain.into_iter().rev() {
 586         if let Some(block) = scopes.block(scope) {
 587             if let Some(def_map) = db.block_def_map(block) {
 588                 let root = def_map.root();
 589                 r = r.push_block_scope(def_map, root);
 590                 // FIXME: This adds as many module scopes as there are blocks, but resolving in each
 591                 // already traverses all parents, so this is O(n²). I think we could only store the
 592                 // innermost module scope instead?
 593             }
 594         }
 595
 596         r = r.push_expr_scope(owner, Arc::clone(&scopes), scope);
 597     }
 598     r
 599 }
 600
 601 impl Resolver {
 602     fn push_scope(mut self, scope: Scope) -> Resolver {
 603         self.scopes.push(scope);
 604         self
 605     }
 606
 607     fn push_generic_params_scope(self, db: &dyn DefDatabase, def: GenericDefId) -> Resolver {
 608         let params = db.generic_params(def);
 609         self.push_scope(Scope::GenericParams { def, params })
 610     }
 611
 612     fn push_impl_def_scope(self, impl_def: ImplId) -> Resolver {
 613         self.push_scope(Scope::ImplDefScope(impl_def))
 614     }
 615
 616     fn push_block_scope(self, def_map: Arc<DefMap>, module_id: LocalModuleId) -> Resolver {
 617         self.push_scope(Scope::BlockScope(ModuleItemMap { def_map, module_id }))
 618     }
 619
 620     fn push_expr_scope(
 621         self,
 622         owner: DefWithBodyId,
 623         expr_scopes: Arc<ExprScopes>,
 624         scope_id: ScopeId,
 625     ) -> Resolver {
 626         self.push_scope(Scope::ExprScope(ExprScope { owner, expr_scopes, scope_id }))
 627     }
 628 }
 629
 630 impl ModuleItemMap {
 631     fn resolve_path_in_value_ns(
 632         &self,
 633         db: &dyn DefDatabase,
 634         path: &ModPath,
 635     ) -> Option<ResolveValueResult> {
 636         let (module_def, idx) =
 637             self.def_map.resolve_path_locally(db, self.module_id, path, BuiltinShadowMode::Other);
 638         match idx {
 639             None => {
 640                 let value = to_value_ns(module_def)?;
 641                 Some(ResolveValueResult::ValueNs(value))
 642             }
 643             Some(idx) => {
 644                 let ty = match module_def.take_types()? {
 645                     ModuleDefId::AdtId(it) => TypeNs::AdtId(it),
 646                     ModuleDefId::TraitId(it) => TypeNs::TraitId(it),
 647                     ModuleDefId::TypeAliasId(it) => TypeNs::TypeAliasId(it),
 648                     ModuleDefId::BuiltinType(it) => TypeNs::BuiltinType(it),
 649
 650                     ModuleDefId::ModuleId(_)
 651                     | ModuleDefId::FunctionId(_)
 652                     | ModuleDefId::EnumVariantId(_)
 653                     | ModuleDefId::ConstId(_)
 654                     | ModuleDefId::MacroId(_)
 655                     | ModuleDefId::StaticId(_) => return None,
 656                 };
 657                 Some(ResolveValueResult::Partial(ty, idx))
 658             }
 659         }
 660     }
 661
 662     fn resolve_path_in_type_ns(
 663         &self,
 664         db: &dyn DefDatabase,
 665         path: &ModPath,
 666     ) -> Option<(TypeNs, Option<usize>)> {
 667         let (module_def, idx) =
 668             self.def_map.resolve_path_locally(db, self.module_id, path, BuiltinShadowMode::Other);
 669         let res = to_type_ns(module_def)?;
 670         Some((res, idx))
 671     }
 672 }
 673
 674 fn to_value_ns(per_ns: PerNs) -> Option<ValueNs> {
 675     let res = match per_ns.take_values()? {
 676         ModuleDefId::FunctionId(it) => ValueNs::FunctionId(it),
 677         ModuleDefId::AdtId(AdtId::StructId(it)) => ValueNs::StructId(it),
 678         ModuleDefId::EnumVariantId(it) => ValueNs::EnumVariantId(it),
 679         ModuleDefId::ConstId(it) => ValueNs::ConstId(it),
 680         ModuleDefId::StaticId(it) => ValueNs::StaticId(it),
 681
 682         ModuleDefId::AdtId(AdtId::EnumId(_) | AdtId::UnionId(_))
 683         | ModuleDefId::TraitId(_)
 684         | ModuleDefId::TypeAliasId(_)
 685         | ModuleDefId::BuiltinType(_)
 686         | ModuleDefId::MacroId(_)
 687         | ModuleDefId::ModuleId(_) => return None,
 688     };
 689     Some(res)
 690 }
 691
 692 fn to_type_ns(per_ns: PerNs) -> Option<TypeNs> {
 693     let res = match per_ns.take_types()? {
 694         ModuleDefId::AdtId(it) => TypeNs::AdtId(it),
 695         ModuleDefId::EnumVariantId(it) => TypeNs::EnumVariantId(it),
 696
 697         ModuleDefId::TypeAliasId(it) => TypeNs::TypeAliasId(it),
 698         ModuleDefId::BuiltinType(it) => TypeNs::BuiltinType(it),
 699
 700         ModuleDefId::TraitId(it) => TypeNs::TraitId(it),
 701
 702         ModuleDefId::FunctionId(_)
 703         | ModuleDefId::ConstId(_)
 704         | ModuleDefId::MacroId(_)
 705         | ModuleDefId::StaticId(_)
 706         | ModuleDefId::ModuleId(_) => return None,
 707     };
 708     Some(res)
 709 }
 710
 711 type FxIndexMap<K, V> = IndexMap<K, V, BuildHasherDefault<rustc_hash::FxHasher>>;
 712 #[derive(Default)]
 713 struct ScopeNames {
 714     map: FxIndexMap<Name, SmallVec<[ScopeDef; 1]>>,
 715 }
 716
 717 impl ScopeNames {
 718     fn add(&mut self, name: &Name, def: ScopeDef) {
 719         let set = self.map.entry(name.clone()).or_default();
 720         if !set.contains(&def) {
 721             set.push(def)
 722         }
 723     }
 724     fn add_per_ns(&mut self, name: &Name, def: PerNs) {
 725         if let &Some((ty, _)) = &def.types {
 726             self.add(name, ScopeDef::ModuleDef(ty))
 727         }
 728         if let &Some((def, _)) = &def.values {
 729             self.add(name, ScopeDef::ModuleDef(def))
 730         }
 731         if let &Some((mac, _)) = &def.macros {
 732             self.add(name, ScopeDef::ModuleDef(ModuleDefId::MacroId(mac)))
 733         }
 734         if def.is_none() {
 735             self.add(name, ScopeDef::Unknown)
 736         }
 737     }
 738     fn add_local(&mut self, name: &Name, pat: PatId) {
 739         let set = self.map.entry(name.clone()).or_default();
 740         // XXX: hack, account for local (and only local) shadowing.
 741         //
 742         // This should be somewhat more principled and take namespaces into
 743         // accounts, but, alas, scoping rules are a hoax. `str` type and `str`
 744         // module can be both available in the same scope.
 745         if set.iter().any(|it| matches!(it, &ScopeDef::Local(_))) {
 746             cov_mark::hit!(shadowing_shows_single_completion);
 747             return;
 748         }
 749         set.push(ScopeDef::Local(pat))
 750     }
 751 }
 752
 753 pub trait HasResolver: Copy {
 754     /// Builds a resolver for type references inside this def.
 755     fn resolver(self, db: &dyn DefDatabase) -> Resolver;
 756 }
 757
 758 impl HasResolver for ModuleId {
 759     fn resolver(self, db: &dyn DefDatabase) -> Resolver {
 760         let mut def_map = self.def_map(db);
 761         let mut modules: SmallVec<[_; 1]> = smallvec![];
 762         let mut module_id = self.local_id;
 763         while let Some(parent) = def_map.parent() {
 764             modules.push((def_map, module_id));
 765             def_map = parent.def_map(db);
 766             module_id = parent.local_id;
 767         }
 768         let mut resolver = Resolver {
 769             scopes: Vec::with_capacity(modules.len()),
 770             module_scope: ModuleItemMap { def_map, module_id },
 771         };
 772         for (def_map, module) in modules.into_iter().rev() {
 773             resolver = resolver.push_block_scope(def_map, module);
 774         }
 775         resolver
 776     }
 777 }
 778
 779 impl HasResolver for TraitId {
 780     fn resolver(self, db: &dyn DefDatabase) -> Resolver {
 781         self.lookup(db).container.resolver(db).push_generic_params_scope(db, self.into())
 782     }
 783 }
 784
 785 impl<T: Into<AdtId> + Copy> HasResolver for T {
 786     fn resolver(self, db: &dyn DefDatabase) -> Resolver {
 787         let def = self.into();
 788         def.module(db)
 789             .resolver(db)
 790             .push_generic_params_scope(db, def.into())
 791             .push_scope(Scope::AdtScope(def))
 792     }
 793 }
 794
 795 impl HasResolver for FunctionId {
 796     fn resolver(self, db: &dyn DefDatabase) -> Resolver {
 797         self.lookup(db).container.resolver(db).push_generic_params_scope(db, self.into())
 798     }
 799 }
 800
 801 impl HasResolver for ConstId {
 802     fn resolver(self, db: &dyn DefDatabase) -> Resolver {
 803         self.lookup(db).container.resolver(db)
 804     }
 805 }
 806
 807 impl HasResolver for StaticId {
 808     fn resolver(self, db: &dyn DefDatabase) -> Resolver {
 809         self.lookup(db).container.resolver(db)
 810     }
 811 }
 812
 813 impl HasResolver for TypeAliasId {
 814     fn resolver(self, db: &dyn DefDatabase) -> Resolver {
 815         self.lookup(db).container.resolver(db).push_generic_params_scope(db, self.into())
 816     }
 817 }
 818
 819 impl HasResolver for ImplId {
 820     fn resolver(self, db: &dyn DefDatabase) -> Resolver {
 821         self.lookup(db)
 822             .container
 823             .resolver(db)
 824             .push_generic_params_scope(db, self.into())
 825             .push_impl_def_scope(self)
 826     }
 827 }
 828
 829 impl HasResolver for ExternBlockId {
 830     fn resolver(self, db: &dyn DefDatabase) -> Resolver {
 831         // Same as parent's
 832         self.lookup(db).container.resolver(db)
 833     }
 834 }
 835
 836 impl HasResolver for DefWithBodyId {
 837     fn resolver(self, db: &dyn DefDatabase) -> Resolver {
 838         match self {
 839             DefWithBodyId::ConstId(c) => c.resolver(db),
 840             DefWithBodyId::FunctionId(f) => f.resolver(db),
 841             DefWithBodyId::StaticId(s) => s.resolver(db),
 842         }
 843     }
 844 }
 845
 846 impl HasResolver for ItemContainerId {
 847     fn resolver(self, db: &dyn DefDatabase) -> Resolver {
 848         match self {
 849             ItemContainerId::ModuleId(it) => it.resolver(db),
 850             ItemContainerId::TraitId(it) => it.resolver(db),
 851             ItemContainerId::ImplId(it) => it.resolver(db),
 852             ItemContainerId::ExternBlockId(it) => it.resolver(db),
 853         }
 854     }
 855 }
 856
 857 impl HasResolver for GenericDefId {
 858     fn resolver(self, db: &dyn DefDatabase) -> Resolver {
 859         match self {
 860             GenericDefId::FunctionId(inner) => inner.resolver(db),
 861             GenericDefId::AdtId(adt) => adt.resolver(db),
 862             GenericDefId::TraitId(inner) => inner.resolver(db),
 863             GenericDefId::TypeAliasId(inner) => inner.resolver(db),
 864             GenericDefId::ImplId(inner) => inner.resolver(db),
 865             GenericDefId::EnumVariantId(inner) => inner.parent.resolver(db),
 866             GenericDefId::ConstId(inner) => inner.resolver(db),
 867         }
 868     }
 869 }
 870
 871 impl HasResolver for VariantId {
 872     fn resolver(self, db: &dyn DefDatabase) -> Resolver {
 873         match self {
 874             VariantId::EnumVariantId(it) => it.parent.resolver(db),
 875             VariantId::StructId(it) => it.resolver(db),
 876             VariantId::UnionId(it) => it.resolver(db),
 877         }
 878     }
 879 }
 880
 881 impl HasResolver for MacroId {
 882     fn resolver(self, db: &dyn DefDatabase) -> Resolver {
 883         match self {
 884             MacroId::Macro2Id(it) => it.resolver(db),
 885             MacroId::MacroRulesId(it) => it.resolver(db),
 886             MacroId::ProcMacroId(it) => it.resolver(db),
 887         }
 888     }
 889 }
 890
 891 impl HasResolver for Macro2Id {
 892     fn resolver(self, db: &dyn DefDatabase) -> Resolver {
 893         self.lookup(db).container.resolver(db)
 894     }
 895 }
 896
 897 impl HasResolver for ProcMacroId {
 898     fn resolver(self, db: &dyn DefDatabase) -> Resolver {
 899         self.lookup(db).container.resolver(db)
 900     }
 901 }
 902
 903 impl HasResolver for MacroRulesId {
 904     fn resolver(self, db: &dyn DefDatabase) -> Resolver {
 905         self.lookup(db).container.resolver(db)
 906     }
 907 }