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, AssocItemId, ConstId, ConstParamId, DefWithBodyId, EnumId,
24 EnumVariantId, FunctionId, GenericDefId, GenericParamId, HasModule, ImplId, LifetimeParamId,
25 LocalModuleId, Lookup, ModuleDefId, ModuleId, StaticId, StructId, TraitId, TypeAliasId,
26 TypeParamId, VariantId,
29 #[derive(Debug, Clone, Default)]
31 /// The stack of scopes, where the inner-most scope is the last item.
33 /// When using, you generally want to process the scopes in reverse order,
34 /// there's `scopes` *method* for that.
38 // FIXME how to store these best
39 #[derive(Debug, Clone)]
40 struct ModuleItemMap {
42 module_id: LocalModuleId,
45 #[derive(Debug, Clone)]
48 expr_scopes: Arc<ExprScopes>,
52 #[derive(Debug, Clone)]
54 /// All the items and imported names of a module
55 ModuleScope(ModuleItemMap),
56 /// Brings the generic parameters of an item into scope
57 GenericParams { def: GenericDefId, params: Interned<GenericParams> },
58 /// Brings `Self` in `impl` block into scope
60 /// Brings `Self` in enum, struct and union definitions into scope
66 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
69 GenericParam(TypeParamId),
72 // Yup, enum variants are added to the types ns, but any usage of variant as
74 EnumVariantId(EnumVariantId),
75 TypeAliasId(TypeAliasId),
76 BuiltinType(BuiltinType),
78 // Module belong to type ns, but the resolver is used when all module paths
79 // are fully resolved.
83 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
84 pub enum ResolveValueResult {
86 Partial(TypeNs, usize),
89 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
93 FunctionId(FunctionId),
97 EnumVariantId(EnumVariantId),
98 GenericParam(ConstParamId),
102 /// Resolve known trait from std, like `std::futures::Future`
103 pub fn resolve_known_trait(&self, db: &dyn DefDatabase, path: &ModPath) -> Option<TraitId> {
104 let res = self.resolve_module_path(db, path, BuiltinShadowMode::Other).take_types()?;
106 ModuleDefId::TraitId(it) => Some(it),
111 /// Resolve known struct from std, like `std::boxed::Box`
112 pub fn resolve_known_struct(&self, db: &dyn DefDatabase, path: &ModPath) -> Option<StructId> {
113 let res = self.resolve_module_path(db, path, BuiltinShadowMode::Other).take_types()?;
115 ModuleDefId::AdtId(AdtId::StructId(it)) => Some(it),
120 /// Resolve known enum from std, like `std::result::Result`
121 pub fn resolve_known_enum(&self, db: &dyn DefDatabase, path: &ModPath) -> Option<EnumId> {
122 let res = self.resolve_module_path(db, path, BuiltinShadowMode::Other).take_types()?;
124 ModuleDefId::AdtId(AdtId::EnumId(it)) => Some(it),
129 fn scopes(&self) -> impl Iterator<Item = &Scope> {
130 self.scopes.iter().rev()
133 fn resolve_module_path(
135 db: &dyn DefDatabase,
137 shadow: BuiltinShadowMode,
139 let (item_map, module) = match self.module_scope() {
141 None => return PerNs::none(),
143 let (module_res, segment_index) = item_map.resolve_path(db, module, path, shadow);
144 if segment_index.is_some() {
145 return PerNs::none();
150 pub fn resolve_module_path_in_items(&self, db: &dyn DefDatabase, path: &ModPath) -> PerNs {
151 self.resolve_module_path(db, path, BuiltinShadowMode::Module)
154 pub fn resolve_module_path_in_trait_assoc_items(
156 db: &dyn DefDatabase,
159 let (item_map, module) = self.module_scope()?;
160 let (module_res, idx) = item_map.resolve_path(db, module, path, BuiltinShadowMode::Module);
161 match module_res.take_types()? {
162 ModuleDefId::TraitId(it) => {
164 let unresolved = &path.segments()[idx..];
165 let assoc = match unresolved {
169 let &(_, assoc) = db.trait_data(it).items.iter().find(|(n, _)| n == assoc)?;
171 AssocItemId::FunctionId(it) => PerNs::values(it.into(), Visibility::Public),
172 AssocItemId::ConstId(it) => PerNs::values(it.into(), Visibility::Public),
173 AssocItemId::TypeAliasId(it) => PerNs::types(it.into(), Visibility::Public),
180 pub fn resolve_path_in_type_ns(
182 db: &dyn DefDatabase,
184 ) -> Option<(TypeNs, Option<usize>)> {
185 let first_name = path.segments().first()?;
186 let skip_to_mod = path.kind != PathKind::Plain;
187 for scope in self.scopes() {
189 Scope::ExprScope(_) => continue,
190 Scope::GenericParams { .. } | Scope::ImplDefScope(_) if skip_to_mod => continue,
192 Scope::GenericParams { params, def } => {
193 if let Some(local_id) = params.find_type_by_name(first_name) {
194 let idx = if path.segments().len() == 1 { None } else { Some(1) };
196 TypeNs::GenericParam(TypeParamId { local_id, parent: *def }),
201 Scope::ImplDefScope(impl_) => {
202 if first_name == &name![Self] {
203 let idx = if path.segments().len() == 1 { None } else { Some(1) };
204 return Some((TypeNs::SelfType(*impl_), idx));
207 Scope::AdtScope(adt) => {
208 if first_name == &name![Self] {
209 let idx = if path.segments().len() == 1 { None } else { Some(1) };
210 return Some((TypeNs::AdtSelfType(*adt), idx));
213 Scope::ModuleScope(m) => {
214 if let Some(res) = m.resolve_path_in_type_ns(db, path) {
223 pub fn resolve_path_in_type_ns_fully(
225 db: &dyn DefDatabase,
227 ) -> Option<TypeNs> {
228 let (res, unresolved) = self.resolve_path_in_type_ns(db, path)?;
229 if unresolved.is_some() {
235 pub fn resolve_visibility(
237 db: &dyn DefDatabase,
238 visibility: &RawVisibility,
239 ) -> Option<Visibility> {
241 RawVisibility::Module(_) => {
242 let (item_map, module) = match self.module_scope() {
246 item_map.resolve_visibility(db, module, visibility)
248 RawVisibility::Public => Some(Visibility::Public),
252 pub fn resolve_path_in_value_ns(
254 db: &dyn DefDatabase,
256 ) -> Option<ResolveValueResult> {
257 let n_segments = path.segments().len();
258 let tmp = name![self];
259 let first_name = if path.is_self() { &tmp } else { path.segments().first()? };
260 let skip_to_mod = path.kind != PathKind::Plain && !path.is_self();
261 for scope in self.scopes() {
264 | Scope::ExprScope(_)
265 | Scope::GenericParams { .. }
266 | Scope::ImplDefScope(_)
272 Scope::ExprScope(scope) if n_segments <= 1 => {
275 .entries(scope.scope_id)
277 .find(|entry| entry.name() == first_name);
279 if let Some(e) = entry {
280 return Some(ResolveValueResult::ValueNs(ValueNs::LocalBinding(e.pat())));
283 Scope::ExprScope(_) => continue,
285 Scope::GenericParams { params, def } if n_segments > 1 => {
286 if let Some(local_id) = params.find_type_by_name(first_name) {
287 let ty = TypeNs::GenericParam(TypeParamId { local_id, parent: *def });
288 return Some(ResolveValueResult::Partial(ty, 1));
291 Scope::GenericParams { params, def } if n_segments == 1 => {
292 if let Some(local_id) = params.find_const_by_name(first_name) {
293 let val = ValueNs::GenericParam(ConstParamId { local_id, parent: *def });
294 return Some(ResolveValueResult::ValueNs(val));
297 Scope::GenericParams { .. } => continue,
299 Scope::ImplDefScope(impl_) => {
300 if first_name == &name![Self] {
302 let ty = TypeNs::SelfType(*impl_);
303 return Some(ResolveValueResult::Partial(ty, 1));
305 return Some(ResolveValueResult::ValueNs(ValueNs::ImplSelf(*impl_)));
309 Scope::AdtScope(adt) => {
311 // bare `Self` doesn't work in the value namespace in a struct/enum definition
314 if first_name == &name![Self] {
315 let ty = TypeNs::AdtSelfType(*adt);
316 return Some(ResolveValueResult::Partial(ty, 1));
320 Scope::ModuleScope(m) => {
321 if let Some(def) = m.resolve_path_in_value_ns(db, path) {
331 pub fn resolve_path_in_value_ns_fully(
333 db: &dyn DefDatabase,
335 ) -> Option<ValueNs> {
336 match self.resolve_path_in_value_ns(db, path)? {
337 ResolveValueResult::ValueNs(it) => Some(it),
338 ResolveValueResult::Partial(..) => None,
342 pub fn resolve_path_as_macro(
344 db: &dyn DefDatabase,
346 ) -> Option<MacroDefId> {
347 let (item_map, module) = self.module_scope()?;
348 item_map.resolve_path(db, module, path, BuiltinShadowMode::Other).0.take_macros()
351 pub fn process_all_names(&self, db: &dyn DefDatabase, f: &mut dyn FnMut(Name, ScopeDef)) {
352 for scope in self.scopes() {
353 scope.process_names(db, f);
357 pub fn traits_in_scope(&self, db: &dyn DefDatabase) -> FxHashSet<TraitId> {
358 let mut traits = FxHashSet::default();
359 for scope in self.scopes() {
361 Scope::ModuleScope(m) => {
362 if let Some(prelude) = m.def_map.prelude() {
363 let prelude_def_map = prelude.def_map(db);
364 traits.extend(prelude_def_map[prelude.local_id].scope.traits());
366 traits.extend(m.def_map[m.module_id].scope.traits());
368 // Add all traits that are in scope because of the containing DefMaps
369 m.def_map.with_ancestor_maps(db, m.module_id, &mut |def_map, module| {
370 if let Some(prelude) = def_map.prelude() {
371 let prelude_def_map = prelude.def_map(db);
372 traits.extend(prelude_def_map[prelude.local_id].scope.traits());
374 traits.extend(def_map[module].scope.traits());
378 &Scope::ImplDefScope(impl_) => {
379 if let Some(target_trait) = &db.impl_data(impl_).target_trait {
380 if let Some(TypeNs::TraitId(trait_)) =
381 self.resolve_path_in_type_ns_fully(db, target_trait.path.mod_path())
383 traits.insert(trait_);
393 fn module_scope(&self) -> Option<(&DefMap, LocalModuleId)> {
394 self.scopes().find_map(|scope| match scope {
395 Scope::ModuleScope(m) => Some((&*m.def_map, m.module_id)),
401 pub fn module(&self) -> Option<ModuleId> {
402 let (def_map, local_id) = self.module_scope()?;
403 Some(def_map.module_id(local_id))
406 pub fn krate(&self) -> Option<CrateId> {
407 // FIXME: can this ever be `None`?
408 self.module_scope().map(|t| t.0.krate())
411 pub fn where_predicates_in_scope(
413 ) -> impl Iterator<Item = &crate::generics::WherePredicate> {
415 .filter_map(|scope| match scope {
416 Scope::GenericParams { params, .. } => Some(params),
419 .flat_map(|params| params.where_predicates.iter())
422 pub fn generic_def(&self) -> Option<GenericDefId> {
423 self.scopes().find_map(|scope| match scope {
424 Scope::GenericParams { def, .. } => Some(*def),
429 pub fn body_owner(&self) -> Option<DefWithBodyId> {
430 self.scopes().find_map(|scope| match scope {
431 Scope::ExprScope(it) => Some(it.owner),
439 ImplSelfType(ImplId),
441 GenericParam(GenericParamId),
447 fn process_names(&self, db: &dyn DefDatabase, f: &mut dyn FnMut(Name, ScopeDef)) {
448 let mut seen = FxHashSet::default();
450 Scope::ModuleScope(m) => {
451 // FIXME: should we provide `self` here?
453 // Name::self_param(),
454 // PerNs::types(Resolution::Def {
455 // def: m.module.into(),
458 m.def_map[m.module_id].scope.entries().for_each(|(name, def)| {
459 f(name.clone(), ScopeDef::PerNs(def));
461 m.def_map[m.module_id].scope.legacy_macros().for_each(|(name, macro_)| {
462 let scope = PerNs::macros(macro_, Visibility::Public);
463 seen.insert((name.clone(), scope));
464 f(name.clone(), ScopeDef::PerNs(scope));
466 m.def_map.extern_prelude().for_each(|(name, &def)| {
467 f(name.clone(), ScopeDef::PerNs(PerNs::types(def, Visibility::Public)));
469 BUILTIN_SCOPE.iter().for_each(|(name, &def)| {
470 f(name.clone(), ScopeDef::PerNs(def));
472 if let Some(prelude) = m.def_map.prelude() {
473 let prelude_def_map = prelude.def_map(db);
474 prelude_def_map[prelude.local_id].scope.entries().for_each(|(name, def)| {
475 let seen_tuple = (name.clone(), def);
476 if !seen.contains(&seen_tuple) {
477 f(seen_tuple.0, ScopeDef::PerNs(def));
482 Scope::GenericParams { params, def: parent } => {
483 let parent = *parent;
484 for (local_id, param) in params.types.iter() {
485 if let Some(ref name) = param.name {
486 let id = TypeParamId { parent, local_id };
487 f(name.clone(), ScopeDef::GenericParam(id.into()))
490 for (local_id, param) in params.consts.iter() {
491 let id = ConstParamId { parent, local_id };
492 f(param.name.clone(), ScopeDef::GenericParam(id.into()))
494 for (local_id, param) in params.lifetimes.iter() {
495 let id = LifetimeParamId { parent, local_id };
496 f(param.name.clone(), ScopeDef::GenericParam(id.into()))
499 Scope::ImplDefScope(i) => {
500 f(name![Self], ScopeDef::ImplSelfType(*i));
502 Scope::AdtScope(i) => {
503 f(name![Self], ScopeDef::AdtSelfType(*i));
505 Scope::ExprScope(scope) => {
506 if let Some((label, name)) = scope.expr_scopes.label(scope.scope_id) {
507 f(name, ScopeDef::Label(label))
509 scope.expr_scopes.entries(scope.scope_id).iter().for_each(|e| {
510 f(e.name().clone(), ScopeDef::Local(e.pat()));
517 // needs arbitrary_self_types to be a method... or maybe move to the def?
518 pub fn resolver_for_expr(db: &dyn DefDatabase, owner: DefWithBodyId, expr_id: ExprId) -> Resolver {
519 let scopes = db.expr_scopes(owner);
520 resolver_for_scope(db, owner, scopes.scope_for(expr_id))
523 pub fn resolver_for_scope(
524 db: &dyn DefDatabase,
525 owner: DefWithBodyId,
526 scope_id: Option<ScopeId>,
528 let mut r = owner.resolver(db);
529 let scopes = db.expr_scopes(owner);
530 let scope_chain = scopes.scope_chain(scope_id).collect::<Vec<_>>();
531 for scope in scope_chain.into_iter().rev() {
532 if let Some(block) = scopes.block(scope) {
533 if let Some(def_map) = db.block_def_map(block) {
534 let root = def_map.root();
535 r = r.push_module_scope(def_map, root);
536 // FIXME: This adds as many module scopes as there are blocks, but resolving in each
537 // already traverses all parents, so this is O(n²). I think we could only store the
538 // innermost module scope instead?
542 r = r.push_expr_scope(owner, Arc::clone(&scopes), scope);
548 fn push_scope(mut self, scope: Scope) -> Resolver {
549 self.scopes.push(scope);
553 fn push_generic_params_scope(self, db: &dyn DefDatabase, def: GenericDefId) -> Resolver {
554 let params = db.generic_params(def);
555 self.push_scope(Scope::GenericParams { def, params })
558 fn push_impl_def_scope(self, impl_def: ImplId) -> Resolver {
559 self.push_scope(Scope::ImplDefScope(impl_def))
562 fn push_module_scope(self, def_map: Arc<DefMap>, module_id: LocalModuleId) -> Resolver {
563 self.push_scope(Scope::ModuleScope(ModuleItemMap { def_map, module_id }))
568 owner: DefWithBodyId,
569 expr_scopes: Arc<ExprScopes>,
572 self.push_scope(Scope::ExprScope(ExprScope { owner, expr_scopes, scope_id }))
577 fn resolve_path_in_value_ns(
579 db: &dyn DefDatabase,
581 ) -> Option<ResolveValueResult> {
582 let (module_def, idx) =
583 self.def_map.resolve_path_locally(db, self.module_id, path, BuiltinShadowMode::Other);
586 let value = to_value_ns(module_def)?;
587 Some(ResolveValueResult::ValueNs(value))
590 let ty = match module_def.take_types()? {
591 ModuleDefId::AdtId(it) => TypeNs::AdtId(it),
592 ModuleDefId::TraitId(it) => TypeNs::TraitId(it),
593 ModuleDefId::TypeAliasId(it) => TypeNs::TypeAliasId(it),
594 ModuleDefId::BuiltinType(it) => TypeNs::BuiltinType(it),
596 ModuleDefId::ModuleId(_)
597 | ModuleDefId::FunctionId(_)
598 | ModuleDefId::EnumVariantId(_)
599 | ModuleDefId::ConstId(_)
600 | ModuleDefId::StaticId(_) => return None,
602 Some(ResolveValueResult::Partial(ty, idx))
607 fn resolve_path_in_type_ns(
609 db: &dyn DefDatabase,
611 ) -> Option<(TypeNs, Option<usize>)> {
612 let (module_def, idx) =
613 self.def_map.resolve_path_locally(db, self.module_id, path, BuiltinShadowMode::Other);
614 let res = to_type_ns(module_def)?;
619 fn to_value_ns(per_ns: PerNs) -> Option<ValueNs> {
620 let res = match per_ns.take_values()? {
621 ModuleDefId::FunctionId(it) => ValueNs::FunctionId(it),
622 ModuleDefId::AdtId(AdtId::StructId(it)) => ValueNs::StructId(it),
623 ModuleDefId::EnumVariantId(it) => ValueNs::EnumVariantId(it),
624 ModuleDefId::ConstId(it) => ValueNs::ConstId(it),
625 ModuleDefId::StaticId(it) => ValueNs::StaticId(it),
627 ModuleDefId::AdtId(AdtId::EnumId(_) | AdtId::UnionId(_))
628 | ModuleDefId::TraitId(_)
629 | ModuleDefId::TypeAliasId(_)
630 | ModuleDefId::BuiltinType(_)
631 | ModuleDefId::ModuleId(_) => return None,
636 fn to_type_ns(per_ns: PerNs) -> Option<TypeNs> {
637 let res = match per_ns.take_types()? {
638 ModuleDefId::AdtId(it) => TypeNs::AdtId(it),
639 ModuleDefId::EnumVariantId(it) => TypeNs::EnumVariantId(it),
641 ModuleDefId::TypeAliasId(it) => TypeNs::TypeAliasId(it),
642 ModuleDefId::BuiltinType(it) => TypeNs::BuiltinType(it),
644 ModuleDefId::TraitId(it) => TypeNs::TraitId(it),
646 ModuleDefId::FunctionId(_)
647 | ModuleDefId::ConstId(_)
648 | ModuleDefId::StaticId(_)
649 | ModuleDefId::ModuleId(_) => return None,
654 pub trait HasResolver: Copy {
655 /// Builds a resolver for type references inside this def.
656 fn resolver(self, db: &dyn DefDatabase) -> Resolver;
659 impl HasResolver for ModuleId {
660 fn resolver(self, db: &dyn DefDatabase) -> Resolver {
661 let mut def_map = self.def_map(db);
662 let mut modules = vec![(def_map.clone(), self.local_id)];
663 while let Some(parent) = def_map.parent() {
664 def_map = parent.def_map(db);
665 modules.push((def_map.clone(), parent.local_id));
667 let mut resolver = Resolver::default();
668 for (def_map, module) in modules.into_iter().rev() {
669 resolver = resolver.push_module_scope(def_map, module);
675 impl HasResolver for TraitId {
676 fn resolver(self, db: &dyn DefDatabase) -> Resolver {
677 self.lookup(db).container.resolver(db).push_generic_params_scope(db, self.into())
681 impl<T: Into<AdtId> + Copy> HasResolver for T {
682 fn resolver(self, db: &dyn DefDatabase) -> Resolver {
683 let def = self.into();
686 .push_generic_params_scope(db, def.into())
687 .push_scope(Scope::AdtScope(def))
691 impl HasResolver for FunctionId {
692 fn resolver(self, db: &dyn DefDatabase) -> Resolver {
693 self.lookup(db).container.resolver(db).push_generic_params_scope(db, self.into())
697 impl HasResolver for ConstId {
698 fn resolver(self, db: &dyn DefDatabase) -> Resolver {
699 self.lookup(db).container.resolver(db)
703 impl HasResolver for StaticId {
704 fn resolver(self, db: &dyn DefDatabase) -> Resolver {
705 self.lookup(db).container.resolver(db)
709 impl HasResolver for TypeAliasId {
710 fn resolver(self, db: &dyn DefDatabase) -> Resolver {
711 self.lookup(db).container.resolver(db).push_generic_params_scope(db, self.into())
715 impl HasResolver for ImplId {
716 fn resolver(self, db: &dyn DefDatabase) -> Resolver {
720 .push_generic_params_scope(db, self.into())
721 .push_impl_def_scope(self)
725 impl HasResolver for DefWithBodyId {
726 fn resolver(self, db: &dyn DefDatabase) -> Resolver {
728 DefWithBodyId::ConstId(c) => c.resolver(db),
729 DefWithBodyId::FunctionId(f) => f.resolver(db),
730 DefWithBodyId::StaticId(s) => s.resolver(db),
735 impl HasResolver for AssocContainerId {
736 fn resolver(self, db: &dyn DefDatabase) -> Resolver {
738 AssocContainerId::ModuleId(it) => it.resolver(db),
739 AssocContainerId::TraitId(it) => it.resolver(db),
740 AssocContainerId::ImplId(it) => it.resolver(db),
745 impl HasResolver for GenericDefId {
746 fn resolver(self, db: &dyn DefDatabase) -> Resolver {
748 GenericDefId::FunctionId(inner) => inner.resolver(db),
749 GenericDefId::AdtId(adt) => adt.resolver(db),
750 GenericDefId::TraitId(inner) => inner.resolver(db),
751 GenericDefId::TypeAliasId(inner) => inner.resolver(db),
752 GenericDefId::ImplId(inner) => inner.resolver(db),
753 GenericDefId::EnumVariantId(inner) => inner.parent.resolver(db),
754 GenericDefId::ConstId(inner) => inner.resolver(db),
759 impl HasResolver for VariantId {
760 fn resolver(self, db: &dyn DefDatabase) -> Resolver {
762 VariantId::EnumVariantId(it) => it.parent.resolver(db),
763 VariantId::StructId(it) => it.resolver(db),
764 VariantId::UnionId(it) => it.resolver(db),