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,
17 item_scope::{BuiltinShadowMode, BUILTIN_SCOPE},
19 path::{ModPath, PathKind},
21 visibility::{RawVisibility, Visibility},
22 AdtId, AssocContainerId, ConstId, ConstParamId, DefWithBodyId, EnumId, EnumVariantId,
23 FunctionId, GenericDefId, GenericParamId, HasModule, ImplId, LifetimeParamId, LocalModuleId,
24 Lookup, ModuleDefId, ModuleId, StaticId, StructId, TraitId, TypeAliasId, TypeParamId,
28 #[derive(Debug, Clone, Default)]
30 // FIXME: all usages generally call `.rev`, so maybe reverse once in construction?
34 // FIXME how to store these best
35 #[derive(Debug, Clone)]
36 struct ModuleItemMap {
38 module_id: LocalModuleId,
41 #[derive(Debug, Clone)]
44 expr_scopes: Arc<ExprScopes>,
48 #[derive(Debug, Clone)]
50 /// All the items and imported names of a module
51 ModuleScope(ModuleItemMap),
52 /// Brings the generic parameters of an item into scope
53 GenericParams { def: GenericDefId, params: Arc<GenericParams> },
54 /// Brings `Self` in `impl` block into scope
56 /// Brings `Self` in enum, struct and union definitions into scope
62 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
65 GenericParam(TypeParamId),
68 // Yup, enum variants are added to the types ns, but any usage of variant as
70 EnumVariantId(EnumVariantId),
71 TypeAliasId(TypeAliasId),
72 BuiltinType(BuiltinType),
74 // Module belong to type ns, but the resolver is used when all module paths
75 // are fully resolved.
79 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
80 pub enum ResolveValueResult {
82 Partial(TypeNs, usize),
85 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
89 FunctionId(FunctionId),
93 EnumVariantId(EnumVariantId),
94 GenericParam(ConstParamId),
98 /// Resolve known trait from std, like `std::futures::Future`
99 pub fn resolve_known_trait(&self, db: &dyn DefDatabase, path: &ModPath) -> Option<TraitId> {
100 let res = self.resolve_module_path(db, path, BuiltinShadowMode::Other).take_types()?;
102 ModuleDefId::TraitId(it) => Some(it),
107 /// Resolve known struct from std, like `std::boxed::Box`
108 pub fn resolve_known_struct(&self, db: &dyn DefDatabase, path: &ModPath) -> Option<StructId> {
109 let res = self.resolve_module_path(db, path, BuiltinShadowMode::Other).take_types()?;
111 ModuleDefId::AdtId(AdtId::StructId(it)) => Some(it),
116 /// Resolve known enum from std, like `std::result::Result`
117 pub fn resolve_known_enum(&self, db: &dyn DefDatabase, path: &ModPath) -> Option<EnumId> {
118 let res = self.resolve_module_path(db, path, BuiltinShadowMode::Other).take_types()?;
120 ModuleDefId::AdtId(AdtId::EnumId(it)) => Some(it),
125 fn resolve_module_path(
127 db: &dyn DefDatabase,
129 shadow: BuiltinShadowMode,
131 let (item_map, module) = match self.module_scope() {
133 None => return PerNs::none(),
135 let (module_res, segment_index) = item_map.resolve_path(db, module, &path, shadow);
136 if segment_index.is_some() {
137 return PerNs::none();
142 pub fn resolve_module_path_in_items(&self, db: &dyn DefDatabase, path: &ModPath) -> PerNs {
143 self.resolve_module_path(db, path, BuiltinShadowMode::Module)
146 pub fn resolve_module_path_in_trait_items(
148 db: &dyn DefDatabase,
150 ) -> Option<TraitId> {
151 let (item_map, module) = self.module_scope()?;
152 let (module_res, ..) = item_map.resolve_path(db, module, &path, BuiltinShadowMode::Module);
153 match module_res.take_types()? {
154 ModuleDefId::TraitId(it) => Some(it),
159 pub fn resolve_path_in_type_ns(
161 db: &dyn DefDatabase,
163 ) -> Option<(TypeNs, Option<usize>)> {
164 let first_name = path.segments().first()?;
165 let skip_to_mod = path.kind != PathKind::Plain;
166 for scope in self.scopes.iter().rev() {
168 Scope::ExprScope(_) => continue,
169 Scope::GenericParams { .. } | Scope::ImplDefScope(_) if skip_to_mod => continue,
171 Scope::GenericParams { params, def } => {
172 if let Some(local_id) = params.find_type_by_name(first_name) {
173 let idx = if path.segments().len() == 1 { None } else { Some(1) };
175 TypeNs::GenericParam(TypeParamId { local_id, parent: *def }),
180 Scope::ImplDefScope(impl_) => {
181 if first_name == &name![Self] {
182 let idx = if path.segments().len() == 1 { None } else { Some(1) };
183 return Some((TypeNs::SelfType(*impl_), idx));
186 Scope::AdtScope(adt) => {
187 if first_name == &name![Self] {
188 let idx = if path.segments().len() == 1 { None } else { Some(1) };
189 return Some((TypeNs::AdtSelfType(*adt), idx));
192 Scope::ModuleScope(m) => {
193 if let Some(res) = m.resolve_path_in_type_ns(db, path) {
202 pub fn resolve_path_in_type_ns_fully(
204 db: &dyn DefDatabase,
206 ) -> Option<TypeNs> {
207 let (res, unresolved) = self.resolve_path_in_type_ns(db, path)?;
208 if unresolved.is_some() {
214 pub fn resolve_visibility(
216 db: &dyn DefDatabase,
217 visibility: &RawVisibility,
218 ) -> Option<Visibility> {
220 RawVisibility::Module(_) => {
221 let (item_map, module) = match self.module_scope() {
225 item_map.resolve_visibility(db, module, visibility)
227 RawVisibility::Public => Some(Visibility::Public),
231 pub fn resolve_path_in_value_ns(
233 db: &dyn DefDatabase,
235 ) -> Option<ResolveValueResult> {
236 let n_segments = path.segments().len();
237 let tmp = name![self];
238 let first_name = if path.is_self() { &tmp } else { path.segments().first()? };
239 let skip_to_mod = path.kind != PathKind::Plain && !path.is_self();
240 for scope in self.scopes.iter().rev() {
243 | Scope::ExprScope(_)
244 | Scope::GenericParams { .. }
245 | Scope::ImplDefScope(_)
251 Scope::ExprScope(scope) if n_segments <= 1 => {
254 .entries(scope.scope_id)
256 .find(|entry| entry.name() == first_name);
258 if let Some(e) = entry {
259 return Some(ResolveValueResult::ValueNs(ValueNs::LocalBinding(e.pat())));
262 Scope::ExprScope(_) => continue,
264 Scope::GenericParams { params, def } if n_segments > 1 => {
265 if let Some(local_id) = params.find_type_by_name(first_name) {
266 let ty = TypeNs::GenericParam(TypeParamId { local_id, parent: *def });
267 return Some(ResolveValueResult::Partial(ty, 1));
270 Scope::GenericParams { params, def } if n_segments == 1 => {
271 if let Some(local_id) = params.find_const_by_name(first_name) {
272 let val = ValueNs::GenericParam(ConstParamId { local_id, parent: *def });
273 return Some(ResolveValueResult::ValueNs(val));
276 Scope::GenericParams { .. } => continue,
278 Scope::ImplDefScope(impl_) => {
279 if first_name == &name![Self] {
281 let ty = TypeNs::SelfType(*impl_);
282 return Some(ResolveValueResult::Partial(ty, 1));
284 return Some(ResolveValueResult::ValueNs(ValueNs::ImplSelf(*impl_)));
288 Scope::AdtScope(adt) => {
290 // bare `Self` doesn't work in the value namespace in a struct/enum definition
293 if first_name == &name![Self] {
294 let ty = TypeNs::AdtSelfType(*adt);
295 return Some(ResolveValueResult::Partial(ty, 1));
299 Scope::ModuleScope(m) => {
300 if let Some(def) = m.resolve_path_in_value_ns(db, path) {
310 pub fn resolve_path_in_value_ns_fully(
312 db: &dyn DefDatabase,
314 ) -> Option<ValueNs> {
315 match self.resolve_path_in_value_ns(db, path)? {
316 ResolveValueResult::ValueNs(it) => Some(it),
317 ResolveValueResult::Partial(..) => None,
321 pub fn resolve_path_as_macro(
323 db: &dyn DefDatabase,
325 ) -> Option<MacroDefId> {
326 let (item_map, module) = self.module_scope()?;
327 item_map.resolve_path(db, module, &path, BuiltinShadowMode::Other).0.take_macros()
330 pub fn process_all_names(&self, db: &dyn DefDatabase, f: &mut dyn FnMut(Name, ScopeDef)) {
331 for scope in self.scopes.iter().rev() {
332 scope.process_names(db, f);
336 pub fn traits_in_scope(&self, db: &dyn DefDatabase) -> FxHashSet<TraitId> {
337 let mut traits = FxHashSet::default();
338 for scope in &self.scopes {
339 if let Scope::ModuleScope(m) = scope {
340 if let Some(prelude) = m.def_map.prelude() {
341 let prelude_def_map = prelude.def_map(db);
342 traits.extend(prelude_def_map[prelude.local_id].scope.traits());
344 traits.extend(m.def_map[m.module_id].scope.traits());
346 // Add all traits that are in scope because of the containing DefMaps
347 m.def_map.with_ancestor_maps(db, m.module_id, &mut |def_map, module| {
348 if let Some(prelude) = def_map.prelude() {
349 let prelude_def_map = prelude.def_map(db);
350 traits.extend(prelude_def_map[prelude.local_id].scope.traits());
352 traits.extend(def_map[module].scope.traits());
360 fn module_scope(&self) -> Option<(&DefMap, LocalModuleId)> {
361 self.scopes.iter().rev().find_map(|scope| match scope {
362 Scope::ModuleScope(m) => Some((&*m.def_map, m.module_id)),
368 pub fn module(&self) -> Option<ModuleId> {
369 let (def_map, local_id) = self.module_scope()?;
370 Some(def_map.module_id(local_id))
373 pub fn krate(&self) -> Option<CrateId> {
374 // FIXME: can this ever be `None`?
375 self.module_scope().map(|t| t.0.krate())
378 pub fn where_predicates_in_scope<'a>(
380 ) -> impl Iterator<Item = &'a crate::generics::WherePredicate> + 'a {
384 .filter_map(|scope| match scope {
385 Scope::GenericParams { params, .. } => Some(params),
388 .flat_map(|params| params.where_predicates.iter())
391 pub fn generic_def(&self) -> Option<GenericDefId> {
392 self.scopes.iter().rev().find_map(|scope| match scope {
393 Scope::GenericParams { def, .. } => Some(*def),
398 pub fn body_owner(&self) -> Option<DefWithBodyId> {
399 self.scopes.iter().rev().find_map(|scope| match scope {
400 Scope::ExprScope(it) => Some(it.owner),
408 ImplSelfType(ImplId),
410 GenericParam(GenericParamId),
416 fn process_names(&self, db: &dyn DefDatabase, f: &mut dyn FnMut(Name, ScopeDef)) {
417 let mut seen = FxHashSet::default();
419 Scope::ModuleScope(m) => {
420 // FIXME: should we provide `self` here?
422 // Name::self_param(),
423 // PerNs::types(Resolution::Def {
424 // def: m.module.into(),
427 m.def_map[m.module_id].scope.entries().for_each(|(name, def)| {
428 f(name.clone(), ScopeDef::PerNs(def));
430 m.def_map[m.module_id].scope.legacy_macros().for_each(|(name, macro_)| {
431 let scope = PerNs::macros(macro_, Visibility::Public);
432 seen.insert((name.clone(), scope));
433 f(name.clone(), ScopeDef::PerNs(scope));
435 m.def_map.extern_prelude().for_each(|(name, &def)| {
436 f(name.clone(), ScopeDef::PerNs(PerNs::types(def, Visibility::Public)));
438 BUILTIN_SCOPE.iter().for_each(|(name, &def)| {
439 f(name.clone(), ScopeDef::PerNs(def));
441 if let Some(prelude) = m.def_map.prelude() {
442 let prelude_def_map = prelude.def_map(db);
443 prelude_def_map[prelude.local_id].scope.entries().for_each(|(name, def)| {
444 let seen_tuple = (name.clone(), def);
445 if !seen.contains(&seen_tuple) {
446 f(seen_tuple.0, ScopeDef::PerNs(def));
451 &Scope::GenericParams { ref params, def: parent } => {
452 for (local_id, param) in params.types.iter() {
453 if let Some(ref name) = param.name {
454 let id = TypeParamId { local_id, parent };
455 f(name.clone(), ScopeDef::GenericParam(id.into()))
458 for (local_id, param) in params.consts.iter() {
459 let id = ConstParamId { local_id, parent };
460 f(param.name.clone(), ScopeDef::GenericParam(id.into()))
462 for (local_id, param) in params.lifetimes.iter() {
463 let id = LifetimeParamId { local_id, parent };
464 f(param.name.clone(), ScopeDef::GenericParam(id.into()))
467 Scope::ImplDefScope(i) => {
468 f(name![Self], ScopeDef::ImplSelfType(*i));
470 Scope::AdtScope(i) => {
471 f(name![Self], ScopeDef::AdtSelfType(*i));
473 Scope::ExprScope(scope) => {
474 if let Some((label, name)) = scope.expr_scopes.label(scope.scope_id) {
475 f(name, ScopeDef::Label(label))
477 scope.expr_scopes.entries(scope.scope_id).iter().for_each(|e| {
478 f(e.name().clone(), ScopeDef::Local(e.pat()));
485 // needs arbitrary_self_types to be a method... or maybe move to the def?
486 pub fn resolver_for_expr(db: &dyn DefDatabase, owner: DefWithBodyId, expr_id: ExprId) -> Resolver {
487 let scopes = db.expr_scopes(owner);
488 resolver_for_scope(db, owner, scopes.scope_for(expr_id))
491 pub fn resolver_for_scope(
492 db: &dyn DefDatabase,
493 owner: DefWithBodyId,
494 scope_id: Option<ScopeId>,
496 let mut r = owner.resolver(db);
497 let scopes = db.expr_scopes(owner);
498 let scope_chain = scopes.scope_chain(scope_id).collect::<Vec<_>>();
499 for scope in scope_chain.into_iter().rev() {
500 if let Some(block) = scopes.block(scope) {
501 if let Some(def_map) = db.block_def_map(block) {
502 let root = def_map.root();
503 r = r.push_module_scope(def_map, root);
504 // FIXME: This adds as many module scopes as there are blocks, but resolving in each
505 // already traverses all parents, so this is O(n²). I think we could only store the
506 // innermost module scope instead?
510 r = r.push_expr_scope(owner, Arc::clone(&scopes), scope);
516 fn push_scope(mut self, scope: Scope) -> Resolver {
517 self.scopes.push(scope);
521 fn push_generic_params_scope(self, db: &dyn DefDatabase, def: GenericDefId) -> Resolver {
522 let params = db.generic_params(def);
523 self.push_scope(Scope::GenericParams { def, params })
526 fn push_impl_def_scope(self, impl_def: ImplId) -> Resolver {
527 self.push_scope(Scope::ImplDefScope(impl_def))
530 fn push_module_scope(self, def_map: Arc<DefMap>, module_id: LocalModuleId) -> Resolver {
531 self.push_scope(Scope::ModuleScope(ModuleItemMap { def_map, module_id }))
536 owner: DefWithBodyId,
537 expr_scopes: Arc<ExprScopes>,
540 self.push_scope(Scope::ExprScope(ExprScope { owner, expr_scopes, scope_id }))
545 fn resolve_path_in_value_ns(
547 db: &dyn DefDatabase,
549 ) -> Option<ResolveValueResult> {
550 let (module_def, idx) =
551 self.def_map.resolve_path_locally(db, self.module_id, &path, BuiltinShadowMode::Other);
554 let value = to_value_ns(module_def)?;
555 Some(ResolveValueResult::ValueNs(value))
558 let ty = match module_def.take_types()? {
559 ModuleDefId::AdtId(it) => TypeNs::AdtId(it),
560 ModuleDefId::TraitId(it) => TypeNs::TraitId(it),
561 ModuleDefId::TypeAliasId(it) => TypeNs::TypeAliasId(it),
562 ModuleDefId::BuiltinType(it) => TypeNs::BuiltinType(it),
564 ModuleDefId::ModuleId(_)
565 | ModuleDefId::FunctionId(_)
566 | ModuleDefId::EnumVariantId(_)
567 | ModuleDefId::ConstId(_)
568 | ModuleDefId::StaticId(_) => return None,
570 Some(ResolveValueResult::Partial(ty, idx))
575 fn resolve_path_in_type_ns(
577 db: &dyn DefDatabase,
579 ) -> Option<(TypeNs, Option<usize>)> {
580 let (module_def, idx) =
581 self.def_map.resolve_path_locally(db, self.module_id, &path, BuiltinShadowMode::Other);
582 let res = to_type_ns(module_def)?;
587 fn to_value_ns(per_ns: PerNs) -> Option<ValueNs> {
588 let res = match per_ns.take_values()? {
589 ModuleDefId::FunctionId(it) => ValueNs::FunctionId(it),
590 ModuleDefId::AdtId(AdtId::StructId(it)) => ValueNs::StructId(it),
591 ModuleDefId::EnumVariantId(it) => ValueNs::EnumVariantId(it),
592 ModuleDefId::ConstId(it) => ValueNs::ConstId(it),
593 ModuleDefId::StaticId(it) => ValueNs::StaticId(it),
595 ModuleDefId::AdtId(AdtId::EnumId(_))
596 | ModuleDefId::AdtId(AdtId::UnionId(_))
597 | ModuleDefId::TraitId(_)
598 | ModuleDefId::TypeAliasId(_)
599 | ModuleDefId::BuiltinType(_)
600 | ModuleDefId::ModuleId(_) => return None,
605 fn to_type_ns(per_ns: PerNs) -> Option<TypeNs> {
606 let res = match per_ns.take_types()? {
607 ModuleDefId::AdtId(it) => TypeNs::AdtId(it),
608 ModuleDefId::EnumVariantId(it) => TypeNs::EnumVariantId(it),
610 ModuleDefId::TypeAliasId(it) => TypeNs::TypeAliasId(it),
611 ModuleDefId::BuiltinType(it) => TypeNs::BuiltinType(it),
613 ModuleDefId::TraitId(it) => TypeNs::TraitId(it),
615 ModuleDefId::FunctionId(_)
616 | ModuleDefId::ConstId(_)
617 | ModuleDefId::StaticId(_)
618 | ModuleDefId::ModuleId(_) => return None,
623 pub trait HasResolver: Copy {
624 /// Builds a resolver for type references inside this def.
625 fn resolver(self, db: &dyn DefDatabase) -> Resolver;
628 impl HasResolver for ModuleId {
629 fn resolver(self, db: &dyn DefDatabase) -> Resolver {
630 let mut def_map = self.def_map(db);
631 let mut modules = Vec::new();
632 modules.push((def_map.clone(), self.local_id));
633 while let Some(parent) = def_map.parent() {
634 def_map = parent.def_map(db);
635 modules.push((def_map.clone(), parent.local_id));
637 let mut resolver = Resolver::default();
638 for (def_map, module) in modules.into_iter().rev() {
639 resolver = resolver.push_module_scope(def_map, module);
645 impl HasResolver for TraitId {
646 fn resolver(self, db: &dyn DefDatabase) -> Resolver {
647 self.lookup(db).container.resolver(db).push_generic_params_scope(db, self.into())
651 impl<T: Into<AdtId> + Copy> HasResolver for T {
652 fn resolver(self, db: &dyn DefDatabase) -> Resolver {
653 let def = self.into();
656 .push_generic_params_scope(db, def.into())
657 .push_scope(Scope::AdtScope(def))
661 impl HasResolver for FunctionId {
662 fn resolver(self, db: &dyn DefDatabase) -> Resolver {
663 self.lookup(db).container.resolver(db).push_generic_params_scope(db, self.into())
667 impl HasResolver for ConstId {
668 fn resolver(self, db: &dyn DefDatabase) -> Resolver {
669 self.lookup(db).container.resolver(db)
673 impl HasResolver for StaticId {
674 fn resolver(self, db: &dyn DefDatabase) -> Resolver {
675 self.lookup(db).container.resolver(db)
679 impl HasResolver for TypeAliasId {
680 fn resolver(self, db: &dyn DefDatabase) -> Resolver {
681 self.lookup(db).container.resolver(db).push_generic_params_scope(db, self.into())
685 impl HasResolver for ImplId {
686 fn resolver(self, db: &dyn DefDatabase) -> Resolver {
690 .push_generic_params_scope(db, self.into())
691 .push_impl_def_scope(self)
695 impl HasResolver for DefWithBodyId {
696 fn resolver(self, db: &dyn DefDatabase) -> Resolver {
698 DefWithBodyId::ConstId(c) => c.resolver(db),
699 DefWithBodyId::FunctionId(f) => f.resolver(db),
700 DefWithBodyId::StaticId(s) => s.resolver(db),
705 impl HasResolver for AssocContainerId {
706 fn resolver(self, db: &dyn DefDatabase) -> Resolver {
708 AssocContainerId::ModuleId(it) => it.resolver(db),
709 AssocContainerId::TraitId(it) => it.resolver(db),
710 AssocContainerId::ImplId(it) => it.resolver(db),
715 impl HasResolver for GenericDefId {
716 fn resolver(self, db: &dyn DefDatabase) -> Resolver {
718 GenericDefId::FunctionId(inner) => inner.resolver(db),
719 GenericDefId::AdtId(adt) => adt.resolver(db),
720 GenericDefId::TraitId(inner) => inner.resolver(db),
721 GenericDefId::TypeAliasId(inner) => inner.resolver(db),
722 GenericDefId::ImplId(inner) => inner.resolver(db),
723 GenericDefId::EnumVariantId(inner) => inner.parent.resolver(db),
724 GenericDefId::ConstId(inner) => inner.resolver(db),
729 impl HasResolver for VariantId {
730 fn resolver(self, db: &dyn DefDatabase) -> Resolver {
732 VariantId::EnumVariantId(it) => it.parent.resolver(db),
733 VariantId::StructId(it) => it.resolver(db),
734 VariantId::UnionId(it) => it.resolver(db),