crates/hir_def/src/resolver.rs

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