1 //! Name resolution façade.
9 use rustc_hash::FxHashSet;
12 body::scope::{ExprScopes, ScopeId},
13 builtin_type::BuiltinType,
15 expr::{ExprId, LabelId, PatId},
16 generics::GenericParams,
18 item_scope::{BuiltinShadowMode, BUILTIN_SCOPE},
20 path::{ModPath, PathKind},
22 visibility::{RawVisibility, Visibility},
23 AdtId, AssocContainerId, ConstId, ConstParamId, DefWithBodyId, EnumId, EnumVariantId,
24 FunctionId, GenericDefId, GenericParamId, HasModule, ImplId, LifetimeParamId, LocalModuleId,
25 Lookup, ModuleDefId, ModuleId, StaticId, StructId, TraitId, TypeAliasId, TypeParamId,
29 #[derive(Debug, Clone, Default)]
31 // FIXME: all usages generally call `.rev`, so maybe reverse once in construction?
35 // FIXME how to store these best
36 #[derive(Debug, Clone)]
37 struct ModuleItemMap {
39 module_id: LocalModuleId,
42 #[derive(Debug, Clone)]
45 expr_scopes: Arc<ExprScopes>,
49 #[derive(Debug, Clone)]
51 /// All the items and imported names of a module
52 ModuleScope(ModuleItemMap),
53 /// Brings the generic parameters of an item into scope
54 GenericParams { def: GenericDefId, params: Interned<GenericParams> },
55 /// Brings `Self` in `impl` block into scope
57 /// Brings `Self` in enum, struct and union definitions into scope
63 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
66 GenericParam(TypeParamId),
69 // Yup, enum variants are added to the types ns, but any usage of variant as
71 EnumVariantId(EnumVariantId),
72 TypeAliasId(TypeAliasId),
73 BuiltinType(BuiltinType),
75 // Module belong to type ns, but the resolver is used when all module paths
76 // are fully resolved.
80 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
81 pub enum ResolveValueResult {
83 Partial(TypeNs, usize),
86 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
90 FunctionId(FunctionId),
94 EnumVariantId(EnumVariantId),
95 GenericParam(ConstParamId),
99 /// Resolve known trait from std, like `std::futures::Future`
100 pub fn resolve_known_trait(&self, db: &dyn DefDatabase, path: &ModPath) -> Option<TraitId> {
101 let res = self.resolve_module_path(db, path, BuiltinShadowMode::Other).take_types()?;
103 ModuleDefId::TraitId(it) => Some(it),
108 /// Resolve known struct from std, like `std::boxed::Box`
109 pub fn resolve_known_struct(&self, db: &dyn DefDatabase, path: &ModPath) -> Option<StructId> {
110 let res = self.resolve_module_path(db, path, BuiltinShadowMode::Other).take_types()?;
112 ModuleDefId::AdtId(AdtId::StructId(it)) => Some(it),
117 /// Resolve known enum from std, like `std::result::Result`
118 pub fn resolve_known_enum(&self, db: &dyn DefDatabase, path: &ModPath) -> Option<EnumId> {
119 let res = self.resolve_module_path(db, path, BuiltinShadowMode::Other).take_types()?;
121 ModuleDefId::AdtId(AdtId::EnumId(it)) => Some(it),
126 fn resolve_module_path(
128 db: &dyn DefDatabase,
130 shadow: BuiltinShadowMode,
132 let (item_map, module) = match self.module_scope() {
134 None => return PerNs::none(),
136 let (module_res, segment_index) = item_map.resolve_path(db, module, &path, shadow);
137 if segment_index.is_some() {
138 return PerNs::none();
143 pub fn resolve_module_path_in_items(&self, db: &dyn DefDatabase, path: &ModPath) -> PerNs {
144 self.resolve_module_path(db, path, BuiltinShadowMode::Module)
147 pub fn resolve_module_path_in_trait_items(
149 db: &dyn DefDatabase,
151 ) -> Option<TraitId> {
152 let (item_map, module) = self.module_scope()?;
153 let (module_res, ..) = item_map.resolve_path(db, module, &path, BuiltinShadowMode::Module);
154 match module_res.take_types()? {
155 ModuleDefId::TraitId(it) => Some(it),
160 pub fn resolve_path_in_type_ns(
162 db: &dyn DefDatabase,
164 ) -> Option<(TypeNs, Option<usize>)> {
165 let first_name = path.segments().first()?;
166 let skip_to_mod = path.kind != PathKind::Plain;
167 for scope in self.scopes.iter().rev() {
169 Scope::ExprScope(_) => continue,
170 Scope::GenericParams { .. } | Scope::ImplDefScope(_) if skip_to_mod => continue,
172 Scope::GenericParams { params, def } => {
173 if let Some(local_id) = params.find_type_by_name(first_name) {
174 let idx = if path.segments().len() == 1 { None } else { Some(1) };
176 TypeNs::GenericParam(TypeParamId { local_id, parent: *def }),
181 Scope::ImplDefScope(impl_) => {
182 if first_name == &name![Self] {
183 let idx = if path.segments().len() == 1 { None } else { Some(1) };
184 return Some((TypeNs::SelfType(*impl_), idx));
187 Scope::AdtScope(adt) => {
188 if first_name == &name![Self] {
189 let idx = if path.segments().len() == 1 { None } else { Some(1) };
190 return Some((TypeNs::AdtSelfType(*adt), idx));
193 Scope::ModuleScope(m) => {
194 if let Some(res) = m.resolve_path_in_type_ns(db, path) {
203 pub fn resolve_path_in_type_ns_fully(
205 db: &dyn DefDatabase,
207 ) -> Option<TypeNs> {
208 let (res, unresolved) = self.resolve_path_in_type_ns(db, path)?;
209 if unresolved.is_some() {
215 pub fn resolve_visibility(
217 db: &dyn DefDatabase,
218 visibility: &RawVisibility,
219 ) -> Option<Visibility> {
221 RawVisibility::Module(_) => {
222 let (item_map, module) = match self.module_scope() {
226 item_map.resolve_visibility(db, module, visibility)
228 RawVisibility::Public => Some(Visibility::Public),
232 pub fn resolve_path_in_value_ns(
234 db: &dyn DefDatabase,
236 ) -> Option<ResolveValueResult> {
237 let n_segments = path.segments().len();
238 let tmp = name![self];
239 let first_name = if path.is_self() { &tmp } else { path.segments().first()? };
240 let skip_to_mod = path.kind != PathKind::Plain && !path.is_self();
241 for scope in self.scopes.iter().rev() {
244 | Scope::ExprScope(_)
245 | Scope::GenericParams { .. }
246 | Scope::ImplDefScope(_)
252 Scope::ExprScope(scope) if n_segments <= 1 => {
255 .entries(scope.scope_id)
257 .find(|entry| entry.name() == first_name);
259 if let Some(e) = entry {
260 return Some(ResolveValueResult::ValueNs(ValueNs::LocalBinding(e.pat())));
263 Scope::ExprScope(_) => continue,
265 Scope::GenericParams { params, def } if n_segments > 1 => {
266 if let Some(local_id) = params.find_type_by_name(first_name) {
267 let ty = TypeNs::GenericParam(TypeParamId { local_id, parent: *def });
268 return Some(ResolveValueResult::Partial(ty, 1));
271 Scope::GenericParams { params, def } if n_segments == 1 => {
272 if let Some(local_id) = params.find_const_by_name(first_name) {
273 let val = ValueNs::GenericParam(ConstParamId { local_id, parent: *def });
274 return Some(ResolveValueResult::ValueNs(val));
277 Scope::GenericParams { .. } => continue,
279 Scope::ImplDefScope(impl_) => {
280 if first_name == &name![Self] {
282 let ty = TypeNs::SelfType(*impl_);
283 return Some(ResolveValueResult::Partial(ty, 1));
285 return Some(ResolveValueResult::ValueNs(ValueNs::ImplSelf(*impl_)));
289 Scope::AdtScope(adt) => {
291 // bare `Self` doesn't work in the value namespace in a struct/enum definition
294 if first_name == &name![Self] {
295 let ty = TypeNs::AdtSelfType(*adt);
296 return Some(ResolveValueResult::Partial(ty, 1));
300 Scope::ModuleScope(m) => {
301 if let Some(def) = m.resolve_path_in_value_ns(db, path) {
311 pub fn resolve_path_in_value_ns_fully(
313 db: &dyn DefDatabase,
315 ) -> Option<ValueNs> {
316 match self.resolve_path_in_value_ns(db, path)? {
317 ResolveValueResult::ValueNs(it) => Some(it),
318 ResolveValueResult::Partial(..) => None,
322 pub fn resolve_path_as_macro(
324 db: &dyn DefDatabase,
326 ) -> Option<MacroDefId> {
327 let (item_map, module) = self.module_scope()?;
328 item_map.resolve_path(db, module, &path, BuiltinShadowMode::Other).0.take_macros()
331 pub fn process_all_names(&self, db: &dyn DefDatabase, f: &mut dyn FnMut(Name, ScopeDef)) {
332 for scope in self.scopes.iter().rev() {
333 scope.process_names(db, f);
337 pub fn traits_in_scope(&self, db: &dyn DefDatabase) -> FxHashSet<TraitId> {
338 let mut traits = FxHashSet::default();
339 for scope in &self.scopes {
341 Scope::ModuleScope(m) => {
342 if let Some(prelude) = m.def_map.prelude() {
343 let prelude_def_map = prelude.def_map(db);
344 traits.extend(prelude_def_map[prelude.local_id].scope.traits());
346 traits.extend(m.def_map[m.module_id].scope.traits());
348 // Add all traits that are in scope because of the containing DefMaps
349 m.def_map.with_ancestor_maps(db, m.module_id, &mut |def_map, module| {
350 if let Some(prelude) = def_map.prelude() {
351 let prelude_def_map = prelude.def_map(db);
352 traits.extend(prelude_def_map[prelude.local_id].scope.traits());
354 traits.extend(def_map[module].scope.traits());
358 &Scope::ImplDefScope(impl_) => {
359 if let Some(target_trait) = &db.impl_data(impl_).target_trait {
360 if let Some(TypeNs::TraitId(trait_)) =
361 self.resolve_path_in_type_ns_fully(db, target_trait.path.mod_path())
363 traits.insert(trait_);
373 fn module_scope(&self) -> Option<(&DefMap, LocalModuleId)> {
374 self.scopes.iter().rev().find_map(|scope| match scope {
375 Scope::ModuleScope(m) => Some((&*m.def_map, m.module_id)),
381 pub fn module(&self) -> Option<ModuleId> {
382 let (def_map, local_id) = self.module_scope()?;
383 Some(def_map.module_id(local_id))
386 pub fn krate(&self) -> Option<CrateId> {
387 // FIXME: can this ever be `None`?
388 self.module_scope().map(|t| t.0.krate())
391 pub fn where_predicates_in_scope<'a>(
393 ) -> impl Iterator<Item = &'a crate::generics::WherePredicate> + 'a {
397 .filter_map(|scope| match scope {
398 Scope::GenericParams { params, .. } => Some(params),
401 .flat_map(|params| params.where_predicates.iter())
404 pub fn generic_def(&self) -> Option<GenericDefId> {
405 self.scopes.iter().rev().find_map(|scope| match scope {
406 Scope::GenericParams { def, .. } => Some(*def),
411 pub fn body_owner(&self) -> Option<DefWithBodyId> {
412 self.scopes.iter().rev().find_map(|scope| match scope {
413 Scope::ExprScope(it) => Some(it.owner),
421 ImplSelfType(ImplId),
423 GenericParam(GenericParamId),
429 fn process_names(&self, db: &dyn DefDatabase, f: &mut dyn FnMut(Name, ScopeDef)) {
430 let mut seen = FxHashSet::default();
432 Scope::ModuleScope(m) => {
433 // FIXME: should we provide `self` here?
435 // Name::self_param(),
436 // PerNs::types(Resolution::Def {
437 // def: m.module.into(),
440 m.def_map[m.module_id].scope.entries().for_each(|(name, def)| {
441 f(name.clone(), ScopeDef::PerNs(def));
443 m.def_map[m.module_id].scope.legacy_macros().for_each(|(name, macro_)| {
444 let scope = PerNs::macros(macro_, Visibility::Public);
445 seen.insert((name.clone(), scope));
446 f(name.clone(), ScopeDef::PerNs(scope));
448 m.def_map.extern_prelude().for_each(|(name, &def)| {
449 f(name.clone(), ScopeDef::PerNs(PerNs::types(def, Visibility::Public)));
451 BUILTIN_SCOPE.iter().for_each(|(name, &def)| {
452 f(name.clone(), ScopeDef::PerNs(def));
454 if let Some(prelude) = m.def_map.prelude() {
455 let prelude_def_map = prelude.def_map(db);
456 prelude_def_map[prelude.local_id].scope.entries().for_each(|(name, def)| {
457 let seen_tuple = (name.clone(), def);
458 if !seen.contains(&seen_tuple) {
459 f(seen_tuple.0, ScopeDef::PerNs(def));
464 &Scope::GenericParams { ref params, def: parent } => {
465 for (local_id, param) in params.types.iter() {
466 if let Some(ref name) = param.name {
467 let id = TypeParamId { local_id, parent };
468 f(name.clone(), ScopeDef::GenericParam(id.into()))
471 for (local_id, param) in params.consts.iter() {
472 let id = ConstParamId { local_id, parent };
473 f(param.name.clone(), ScopeDef::GenericParam(id.into()))
475 for (local_id, param) in params.lifetimes.iter() {
476 let id = LifetimeParamId { local_id, parent };
477 f(param.name.clone(), ScopeDef::GenericParam(id.into()))
480 Scope::ImplDefScope(i) => {
481 f(name![Self], ScopeDef::ImplSelfType(*i));
483 Scope::AdtScope(i) => {
484 f(name![Self], ScopeDef::AdtSelfType(*i));
486 Scope::ExprScope(scope) => {
487 if let Some((label, name)) = scope.expr_scopes.label(scope.scope_id) {
488 f(name, ScopeDef::Label(label))
490 scope.expr_scopes.entries(scope.scope_id).iter().for_each(|e| {
491 f(e.name().clone(), ScopeDef::Local(e.pat()));
498 // needs arbitrary_self_types to be a method... or maybe move to the def?
499 pub fn resolver_for_expr(db: &dyn DefDatabase, owner: DefWithBodyId, expr_id: ExprId) -> Resolver {
500 let scopes = db.expr_scopes(owner);
501 resolver_for_scope(db, owner, scopes.scope_for(expr_id))
504 pub fn resolver_for_scope(
505 db: &dyn DefDatabase,
506 owner: DefWithBodyId,
507 scope_id: Option<ScopeId>,
509 let mut r = owner.resolver(db);
510 let scopes = db.expr_scopes(owner);
511 let scope_chain = scopes.scope_chain(scope_id).collect::<Vec<_>>();
512 for scope in scope_chain.into_iter().rev() {
513 if let Some(block) = scopes.block(scope) {
514 if let Some(def_map) = db.block_def_map(block) {
515 let root = def_map.root();
516 r = r.push_module_scope(def_map, root);
517 // FIXME: This adds as many module scopes as there are blocks, but resolving in each
518 // already traverses all parents, so this is O(n²). I think we could only store the
519 // innermost module scope instead?
523 r = r.push_expr_scope(owner, Arc::clone(&scopes), scope);
529 fn push_scope(mut self, scope: Scope) -> Resolver {
530 self.scopes.push(scope);
534 fn push_generic_params_scope(self, db: &dyn DefDatabase, def: GenericDefId) -> Resolver {
535 let params = db.generic_params(def);
536 self.push_scope(Scope::GenericParams { def, params })
539 fn push_impl_def_scope(self, impl_def: ImplId) -> Resolver {
540 self.push_scope(Scope::ImplDefScope(impl_def))
543 fn push_module_scope(self, def_map: Arc<DefMap>, module_id: LocalModuleId) -> Resolver {
544 self.push_scope(Scope::ModuleScope(ModuleItemMap { def_map, module_id }))
549 owner: DefWithBodyId,
550 expr_scopes: Arc<ExprScopes>,
553 self.push_scope(Scope::ExprScope(ExprScope { owner, expr_scopes, scope_id }))
558 fn resolve_path_in_value_ns(
560 db: &dyn DefDatabase,
562 ) -> Option<ResolveValueResult> {
563 let (module_def, idx) =
564 self.def_map.resolve_path_locally(db, self.module_id, &path, BuiltinShadowMode::Other);
567 let value = to_value_ns(module_def)?;
568 Some(ResolveValueResult::ValueNs(value))
571 let ty = match module_def.take_types()? {
572 ModuleDefId::AdtId(it) => TypeNs::AdtId(it),
573 ModuleDefId::TraitId(it) => TypeNs::TraitId(it),
574 ModuleDefId::TypeAliasId(it) => TypeNs::TypeAliasId(it),
575 ModuleDefId::BuiltinType(it) => TypeNs::BuiltinType(it),
577 ModuleDefId::ModuleId(_)
578 | ModuleDefId::FunctionId(_)
579 | ModuleDefId::EnumVariantId(_)
580 | ModuleDefId::ConstId(_)
581 | ModuleDefId::StaticId(_) => return None,
583 Some(ResolveValueResult::Partial(ty, idx))
588 fn resolve_path_in_type_ns(
590 db: &dyn DefDatabase,
592 ) -> Option<(TypeNs, Option<usize>)> {
593 let (module_def, idx) =
594 self.def_map.resolve_path_locally(db, self.module_id, &path, BuiltinShadowMode::Other);
595 let res = to_type_ns(module_def)?;
600 fn to_value_ns(per_ns: PerNs) -> Option<ValueNs> {
601 let res = match per_ns.take_values()? {
602 ModuleDefId::FunctionId(it) => ValueNs::FunctionId(it),
603 ModuleDefId::AdtId(AdtId::StructId(it)) => ValueNs::StructId(it),
604 ModuleDefId::EnumVariantId(it) => ValueNs::EnumVariantId(it),
605 ModuleDefId::ConstId(it) => ValueNs::ConstId(it),
606 ModuleDefId::StaticId(it) => ValueNs::StaticId(it),
608 ModuleDefId::AdtId(AdtId::EnumId(_))
609 | ModuleDefId::AdtId(AdtId::UnionId(_))
610 | ModuleDefId::TraitId(_)
611 | ModuleDefId::TypeAliasId(_)
612 | ModuleDefId::BuiltinType(_)
613 | ModuleDefId::ModuleId(_) => return None,
618 fn to_type_ns(per_ns: PerNs) -> Option<TypeNs> {
619 let res = match per_ns.take_types()? {
620 ModuleDefId::AdtId(it) => TypeNs::AdtId(it),
621 ModuleDefId::EnumVariantId(it) => TypeNs::EnumVariantId(it),
623 ModuleDefId::TypeAliasId(it) => TypeNs::TypeAliasId(it),
624 ModuleDefId::BuiltinType(it) => TypeNs::BuiltinType(it),
626 ModuleDefId::TraitId(it) => TypeNs::TraitId(it),
628 ModuleDefId::FunctionId(_)
629 | ModuleDefId::ConstId(_)
630 | ModuleDefId::StaticId(_)
631 | ModuleDefId::ModuleId(_) => return None,
636 pub trait HasResolver: Copy {
637 /// Builds a resolver for type references inside this def.
638 fn resolver(self, db: &dyn DefDatabase) -> Resolver;
641 impl HasResolver for ModuleId {
642 fn resolver(self, db: &dyn DefDatabase) -> Resolver {
643 let mut def_map = self.def_map(db);
644 let mut modules = Vec::new();
645 modules.push((def_map.clone(), self.local_id));
646 while let Some(parent) = def_map.parent() {
647 def_map = parent.def_map(db);
648 modules.push((def_map.clone(), parent.local_id));
650 let mut resolver = Resolver::default();
651 for (def_map, module) in modules.into_iter().rev() {
652 resolver = resolver.push_module_scope(def_map, module);
658 impl HasResolver for TraitId {
659 fn resolver(self, db: &dyn DefDatabase) -> Resolver {
660 self.lookup(db).container.resolver(db).push_generic_params_scope(db, self.into())
664 impl<T: Into<AdtId> + Copy> HasResolver for T {
665 fn resolver(self, db: &dyn DefDatabase) -> Resolver {
666 let def = self.into();
669 .push_generic_params_scope(db, def.into())
670 .push_scope(Scope::AdtScope(def))
674 impl HasResolver for FunctionId {
675 fn resolver(self, db: &dyn DefDatabase) -> Resolver {
676 self.lookup(db).container.resolver(db).push_generic_params_scope(db, self.into())
680 impl HasResolver for ConstId {
681 fn resolver(self, db: &dyn DefDatabase) -> Resolver {
682 self.lookup(db).container.resolver(db)
686 impl HasResolver for StaticId {
687 fn resolver(self, db: &dyn DefDatabase) -> Resolver {
688 self.lookup(db).container.resolver(db)
692 impl HasResolver for TypeAliasId {
693 fn resolver(self, db: &dyn DefDatabase) -> Resolver {
694 self.lookup(db).container.resolver(db).push_generic_params_scope(db, self.into())
698 impl HasResolver for ImplId {
699 fn resolver(self, db: &dyn DefDatabase) -> Resolver {
703 .push_generic_params_scope(db, self.into())
704 .push_impl_def_scope(self)
708 impl HasResolver for DefWithBodyId {
709 fn resolver(self, db: &dyn DefDatabase) -> Resolver {
711 DefWithBodyId::ConstId(c) => c.resolver(db),
712 DefWithBodyId::FunctionId(f) => f.resolver(db),
713 DefWithBodyId::StaticId(s) => s.resolver(db),
718 impl HasResolver for AssocContainerId {
719 fn resolver(self, db: &dyn DefDatabase) -> Resolver {
721 AssocContainerId::ModuleId(it) => it.resolver(db),
722 AssocContainerId::TraitId(it) => it.resolver(db),
723 AssocContainerId::ImplId(it) => it.resolver(db),
728 impl HasResolver for GenericDefId {
729 fn resolver(self, db: &dyn DefDatabase) -> Resolver {
731 GenericDefId::FunctionId(inner) => inner.resolver(db),
732 GenericDefId::AdtId(adt) => adt.resolver(db),
733 GenericDefId::TraitId(inner) => inner.resolver(db),
734 GenericDefId::TypeAliasId(inner) => inner.resolver(db),
735 GenericDefId::ImplId(inner) => inner.resolver(db),
736 GenericDefId::EnumVariantId(inner) => inner.parent.resolver(db),
737 GenericDefId::ConstId(inner) => inner.resolver(db),
742 impl HasResolver for VariantId {
743 fn resolver(self, db: &dyn DefDatabase) -> Resolver {
745 VariantId::EnumVariantId(it) => it.parent.resolver(db),
746 VariantId::StructId(it) => it.resolver(db),
747 VariantId::UnionId(it) => it.resolver(db),