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