1 //! Maps *syntax* of various definitions to their semantic ids.
3 //! This is a very interesting module, and, in some sense, can be considered the
4 //! heart of the IDE parts of rust-analyzer.
6 //! This module solves the following problem:
8 //! Given a piece of syntax, find the corresponding semantic definition (def).
10 //! This problem is a part of more-or-less every IDE feature implemented. Every
11 //! IDE functionality (like goto to definition), conceptually starts with a
12 //! specific cursor position in a file. Starting with this text offset, we first
13 //! figure out what syntactic construct are we at: is this a pattern, an
14 //! expression, an item definition.
16 //! Knowing only the syntax gives us relatively little info. For example,
17 //! looking at the syntax of the function we can realise that it is a part of an
18 //! `impl` block, but we won't be able to tell what trait function the current
19 //! function overrides, and whether it does that correctly. For that, we need to
20 //! go from [`ast::Fn`] to [`crate::Function`], and that's exactly what this
23 //! As syntax trees are values and don't know their place of origin/identity,
24 //! this module also requires [`InFile`] wrappers to understand which specific
25 //! real or macro-expanded file the tree comes from.
27 //! The actual algorithm to resolve syntax to def is curious in two aspects:
30 //! * It uses the inverse algorithm (what is the syntax for this def?)
32 //! Specifically, the algorithm goes like this:
34 //! 1. Find the syntactic container for the syntax. For example, field's
35 //! container is the struct, and structs container is a module.
36 //! 2. Recursively get the def corresponding to container.
37 //! 3. Ask the container def for all child defs. These child defs contain
38 //! the answer and answer's siblings.
39 //! 4. For each child def, ask for it's source.
40 //! 5. The child def whose source is the syntax node we've started with
43 //! It's interesting that both Roslyn and Kotlin contain very similar code
46 //! Let's take a look at Roslyn:
48 //! <https://github.com/dotnet/roslyn/blob/36a0c338d6621cc5fe34b79d414074a95a6a489c/src/Compilers/CSharp/Portable/Compilation/SyntaxTreeSemanticModel.cs#L1403-L1429>
49 //! <https://sourceroslyn.io/#Microsoft.CodeAnalysis.CSharp/Compilation/SyntaxTreeSemanticModel.cs,1403>
51 //! The `GetDeclaredType` takes `Syntax` as input, and returns `Symbol` as
52 //! output. First, it retrieves a `Symbol` for parent `Syntax`:
54 //! * <https://sourceroslyn.io/#Microsoft.CodeAnalysis.CSharp/Compilation/SyntaxTreeSemanticModel.cs,1423>
56 //! Then, it iterates parent symbol's children, looking for one which has the
57 //! same text span as the original node:
59 //! <https://sourceroslyn.io/#Microsoft.CodeAnalysis.CSharp/Compilation/SyntaxTreeSemanticModel.cs,1786>
61 //! Now, let's look at Kotlin:
63 //! <https://github.com/JetBrains/kotlin/blob/a288b8b00e4754a1872b164999c6d3f3b8c8994a/idea/idea-frontend-fir/idea-fir-low-level-api/src/org/jetbrains/kotlin/idea/fir/low/level/api/FirModuleResolveStateImpl.kt#L93-L125>
65 //! This function starts with a syntax node (`KtExpression` is syntax, like all
66 //! `Kt` nodes), and returns a def. It uses
67 //! `getNonLocalContainingOrThisDeclaration` to get syntactic container for a
68 //! current node. Then, `findSourceNonLocalFirDeclaration` gets `Fir` for this
69 //! parent. Finally, `findElementIn` function traverses `Fir` children to find
70 //! one with the same source we originally started with.
72 //! One question is left though -- where does the recursion stops? This happens
73 //! when we get to the file syntax node, which doesn't have a syntactic parent.
74 //! In that case, we loop through all the crates that might contain this file
75 //! and look for a module whose source is the given file.
77 //! Note that the logic in this module is somewhat fundamentally imprecise --
78 //! due to conditional compilation and `#[path]` attributes, there's no
79 //! injective mapping from syntax nodes to defs. This is not an edge case --
80 //! more or less every item in a `lib.rs` is a part of two distinct crates: a
81 //! library with `--cfg test` and a library without.
83 //! At the moment, we don't really handle this well and return the first answer
84 //! that works. Ideally, we should first let the caller to pick a specific
85 //! active crate for a given position, and then provide an API to resolve all
86 //! syntax nodes against this specific crate.
91 child_by_source::ChildBySource,
93 expr::{LabelId, PatId},
95 AdtId, ConstId, ConstParamId, DefWithBodyId, EnumId, EnumVariantId, FieldId, FunctionId,
96 GenericDefId, GenericParamId, ImplId, LifetimeParamId, ModuleId, StaticId, StructId, TraitId,
97 TypeAliasId, TypeParamId, UnionId, VariantId,
99 use hir_expand::{name::AsName, AstId, HirFileId, MacroCallId, MacroDefId, MacroDefKind};
100 use rustc_hash::FxHashMap;
101 use smallvec::SmallVec;
104 ast::{self, HasName},
105 match_ast, AstNode, SyntaxNode,
108 use crate::{db::HirDatabase, InFile};
110 pub(super) type SourceToDefCache = FxHashMap<(ChildContainer, HirFileId), DynMap>;
112 pub(super) struct SourceToDefCtx<'a, 'b> {
113 pub(super) db: &'b dyn HirDatabase,
114 pub(super) cache: &'a mut SourceToDefCache,
117 impl SourceToDefCtx<'_, '_> {
118 pub(super) fn file_to_def(&mut self, file: FileId) -> SmallVec<[ModuleId; 1]> {
119 let _p = profile::span("SourceBinder::to_module_def");
120 let mut mods = SmallVec::new();
121 for &crate_id in self.db.relevant_crates(file).iter() {
122 // FIXME: inner items
123 let crate_def_map = self.db.crate_def_map(crate_id);
126 .modules_for_file(file)
127 .map(|local_id| crate_def_map.module_id(local_id)),
133 pub(super) fn module_to_def(&mut self, src: InFile<ast::Module>) -> Option<ModuleId> {
134 let _p = profile::span("module_to_def");
135 let parent_declaration =
136 src.syntax().ancestors_with_macros_skip_attr_item(self.db.upcast()).skip(1).find_map(
138 let m = ast::Module::cast(it.value.clone())?;
139 Some(it.with_value(m))
143 let parent_module = match parent_declaration {
144 Some(parent_declaration) => self.module_to_def(parent_declaration),
146 let file_id = src.file_id.original_file(self.db.upcast());
147 self.file_to_def(file_id).get(0).copied()
151 let child_name = src.value.name()?.as_name();
152 let def_map = parent_module.def_map(self.db.upcast());
153 let child_id = *def_map[parent_module.local_id].children.get(&child_name)?;
154 Some(def_map.module_id(child_id))
157 pub(super) fn source_file_to_def(&mut self, src: InFile<ast::SourceFile>) -> Option<ModuleId> {
158 let _p = profile::span("source_file_to_def");
159 let file_id = src.file_id.original_file(self.db.upcast());
160 self.file_to_def(file_id).get(0).copied()
163 pub(super) fn trait_to_def(&mut self, src: InFile<ast::Trait>) -> Option<TraitId> {
164 self.to_def(src, keys::TRAIT)
166 pub(super) fn impl_to_def(&mut self, src: InFile<ast::Impl>) -> Option<ImplId> {
167 self.to_def(src, keys::IMPL)
169 pub(super) fn fn_to_def(&mut self, src: InFile<ast::Fn>) -> Option<FunctionId> {
170 self.to_def(src, keys::FUNCTION)
172 pub(super) fn struct_to_def(&mut self, src: InFile<ast::Struct>) -> Option<StructId> {
173 self.to_def(src, keys::STRUCT)
175 pub(super) fn enum_to_def(&mut self, src: InFile<ast::Enum>) -> Option<EnumId> {
176 self.to_def(src, keys::ENUM)
178 pub(super) fn union_to_def(&mut self, src: InFile<ast::Union>) -> Option<UnionId> {
179 self.to_def(src, keys::UNION)
181 pub(super) fn static_to_def(&mut self, src: InFile<ast::Static>) -> Option<StaticId> {
182 self.to_def(src, keys::STATIC)
184 pub(super) fn const_to_def(&mut self, src: InFile<ast::Const>) -> Option<ConstId> {
185 self.to_def(src, keys::CONST)
187 pub(super) fn type_alias_to_def(&mut self, src: InFile<ast::TypeAlias>) -> Option<TypeAliasId> {
188 self.to_def(src, keys::TYPE_ALIAS)
190 pub(super) fn record_field_to_def(&mut self, src: InFile<ast::RecordField>) -> Option<FieldId> {
191 self.to_def(src, keys::RECORD_FIELD)
193 pub(super) fn tuple_field_to_def(&mut self, src: InFile<ast::TupleField>) -> Option<FieldId> {
194 self.to_def(src, keys::TUPLE_FIELD)
196 pub(super) fn enum_variant_to_def(
198 src: InFile<ast::Variant>,
199 ) -> Option<EnumVariantId> {
200 self.to_def(src, keys::VARIANT)
202 pub(super) fn adt_to_def(
204 InFile { file_id, value }: InFile<ast::Adt>,
207 ast::Adt::Enum(it) => self.enum_to_def(InFile::new(file_id, it)).map(AdtId::EnumId),
208 ast::Adt::Struct(it) => {
209 self.struct_to_def(InFile::new(file_id, it)).map(AdtId::StructId)
211 ast::Adt::Union(it) => self.union_to_def(InFile::new(file_id, it)).map(AdtId::UnionId),
214 pub(super) fn bind_pat_to_def(
216 src: InFile<ast::IdentPat>,
217 ) -> Option<(DefWithBodyId, PatId)> {
218 let container = self.find_pat_or_label_container(src.syntax())?;
219 let (_body, source_map) = self.db.body_with_source_map(container);
220 let src = src.map(ast::Pat::from);
221 let pat_id = source_map.node_pat(src.as_ref())?;
222 Some((container, pat_id))
224 pub(super) fn self_param_to_def(
226 src: InFile<ast::SelfParam>,
227 ) -> Option<(DefWithBodyId, PatId)> {
228 let container = self.find_pat_or_label_container(src.syntax())?;
229 let (_body, source_map) = self.db.body_with_source_map(container);
230 let pat_id = source_map.node_self_param(src.as_ref())?;
231 Some((container, pat_id))
233 pub(super) fn label_to_def(
235 src: InFile<ast::Label>,
236 ) -> Option<(DefWithBodyId, LabelId)> {
237 let container = self.find_pat_or_label_container(src.syntax())?;
238 let (_body, source_map) = self.db.body_with_source_map(container);
239 let label_id = source_map.node_label(src.as_ref())?;
240 Some((container, label_id))
243 pub(super) fn item_to_macro_call(&mut self, src: InFile<ast::Item>) -> Option<MacroCallId> {
244 let map = self.dyn_map(src.as_ref())?;
245 map[keys::ATTR_MACRO_CALL].get(&src).copied()
248 pub(super) fn attr_to_derive_macro_call(
250 item: InFile<&ast::Adt>,
251 src: InFile<ast::Attr>,
252 ) -> Option<(AttrId, &[Option<MacroCallId>])> {
253 let map = self.dyn_map(item)?;
254 map[keys::DERIVE_MACRO_CALL].get(&src).map(|(id, ids)| (*id, &**ids))
257 fn to_def<Ast: AstNode + 'static, ID: Copy + 'static>(
262 self.dyn_map(src.as_ref())?[key].get(&src).copied()
265 fn dyn_map<Ast: AstNode + 'static>(&mut self, src: InFile<&Ast>) -> Option<&DynMap> {
266 let container = self.find_container(src.map(|it| it.syntax()))?;
267 Some(self.cache_for(container, src.file_id))
270 fn cache_for(&mut self, container: ChildContainer, file_id: HirFileId) -> &DynMap {
273 .entry((container, file_id))
274 .or_insert_with(|| container.child_by_source(db, file_id))
277 pub(super) fn type_param_to_def(&mut self, src: InFile<ast::TypeParam>) -> Option<TypeParamId> {
278 let container: ChildContainer = self.find_generic_param_container(src.syntax())?.into();
279 let dyn_map = self.cache_for(container, src.file_id);
280 dyn_map[keys::TYPE_PARAM].get(&src).copied()
283 pub(super) fn lifetime_param_to_def(
285 src: InFile<ast::LifetimeParam>,
286 ) -> Option<LifetimeParamId> {
287 let container: ChildContainer = self.find_generic_param_container(src.syntax())?.into();
288 let dyn_map = self.cache_for(container, src.file_id);
289 dyn_map[keys::LIFETIME_PARAM].get(&src).copied()
292 pub(super) fn const_param_to_def(
294 src: InFile<ast::ConstParam>,
295 ) -> Option<ConstParamId> {
296 let container: ChildContainer = self.find_generic_param_container(src.syntax())?.into();
297 let dyn_map = self.cache_for(container, src.file_id);
298 dyn_map[keys::CONST_PARAM].get(&src).copied()
301 pub(super) fn generic_param_to_def(
303 InFile { file_id, value }: InFile<ast::GenericParam>,
304 ) -> Option<GenericParamId> {
306 ast::GenericParam::ConstParam(it) => {
307 self.const_param_to_def(InFile::new(file_id, it)).map(GenericParamId::ConstParamId)
309 ast::GenericParam::LifetimeParam(it) => self
310 .lifetime_param_to_def(InFile::new(file_id, it))
311 .map(GenericParamId::LifetimeParamId),
312 ast::GenericParam::TypeParam(it) => {
313 self.type_param_to_def(InFile::new(file_id, it)).map(GenericParamId::TypeParamId)
318 pub(super) fn macro_to_def(&mut self, src: InFile<ast::Macro>) -> Option<MacroDefId> {
320 self.dyn_map(src.as_ref()).and_then(|it| it[keys::MACRO_CALL].get(&src).copied());
321 if let res @ Some(_) = makro {
325 // Not all macros are recorded in the dyn map, only the ones behaving like items, so fall back
326 // for the non-item like definitions.
327 let file_ast_id = self.db.ast_id_map(src.file_id).ast_id(&src.value);
328 let ast_id = AstId::new(src.file_id, file_ast_id.upcast());
329 let kind = MacroDefKind::Declarative(ast_id);
330 let file_id = src.file_id.original_file(self.db.upcast());
331 let krate = self.file_to_def(file_id).get(0).copied()?.krate();
332 Some(MacroDefId { krate, kind, local_inner: false })
335 pub(super) fn find_container(&mut self, src: InFile<&SyntaxNode>) -> Option<ChildContainer> {
336 for container in src.ancestors_with_macros_skip_attr_item(self.db.upcast()).skip(1) {
337 if let Some(res) = self.container_to_def(container) {
342 let def = self.file_to_def(src.file_id.original_file(self.db.upcast())).get(0).copied()?;
346 fn container_to_def(&mut self, container: InFile<SyntaxNode>) -> Option<ChildContainer> {
347 let cont = match_ast! {
348 match (container.value) {
350 let def = self.module_to_def(container.with_value(it))?;
354 let def = self.trait_to_def(container.with_value(it))?;
358 let def = self.impl_to_def(container.with_value(it))?;
362 let def = self.fn_to_def(container.with_value(it))?;
363 DefWithBodyId::from(def).into()
366 let def = self.struct_to_def(container.with_value(it))?;
367 VariantId::from(def).into()
370 let def = self.enum_to_def(container.with_value(it))?;
374 let def = self.union_to_def(container.with_value(it))?;
375 VariantId::from(def).into()
378 let def = self.static_to_def(container.with_value(it))?;
379 DefWithBodyId::from(def).into()
382 let def = self.const_to_def(container.with_value(it))?;
383 DefWithBodyId::from(def).into()
385 ast::TypeAlias(it) => {
386 let def = self.type_alias_to_def(container.with_value(it))?;
389 ast::Variant(it) => {
390 let def = self.enum_variant_to_def(container.with_value(it))?;
391 VariantId::from(def).into()
399 fn find_generic_param_container(&mut self, src: InFile<&SyntaxNode>) -> Option<GenericDefId> {
400 for container in src.ancestors_with_macros_skip_attr_item(self.db.upcast()).skip(1) {
401 let res: GenericDefId = match_ast! {
402 match (container.value) {
403 ast::Fn(it) => self.fn_to_def(container.with_value(it))?.into(),
404 ast::Struct(it) => self.struct_to_def(container.with_value(it))?.into(),
405 ast::Enum(it) => self.enum_to_def(container.with_value(it))?.into(),
406 ast::Trait(it) => self.trait_to_def(container.with_value(it))?.into(),
407 ast::TypeAlias(it) => self.type_alias_to_def(container.with_value(it))?.into(),
408 ast::Impl(it) => self.impl_to_def(container.with_value(it))?.into(),
417 fn find_pat_or_label_container(&mut self, src: InFile<&SyntaxNode>) -> Option<DefWithBodyId> {
418 for container in src.ancestors_with_macros_skip_attr_item(self.db.upcast()).skip(1) {
419 let res: DefWithBodyId = match_ast! {
420 match (container.value) {
421 ast::Const(it) => self.const_to_def(container.with_value(it))?.into(),
422 ast::Static(it) => self.static_to_def(container.with_value(it))?.into(),
423 ast::Fn(it) => self.fn_to_def(container.with_value(it))?.into(),
433 #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
434 pub(crate) enum ChildContainer {
435 DefWithBodyId(DefWithBodyId),
440 VariantId(VariantId),
441 TypeAliasId(TypeAliasId),
442 /// XXX: this might be the same def as, for example an `EnumId`. However,
443 /// here the children are generic parameters, and not, eg enum variants.
444 GenericDefId(GenericDefId),
458 impl ChildContainer {
459 fn child_by_source(self, db: &dyn HirDatabase, file_id: HirFileId) -> DynMap {
460 let db = db.upcast();
462 ChildContainer::DefWithBodyId(it) => it.child_by_source(db, file_id),
463 ChildContainer::ModuleId(it) => it.child_by_source(db, file_id),
464 ChildContainer::TraitId(it) => it.child_by_source(db, file_id),
465 ChildContainer::ImplId(it) => it.child_by_source(db, file_id),
466 ChildContainer::EnumId(it) => it.child_by_source(db, file_id),
467 ChildContainer::VariantId(it) => it.child_by_source(db, file_id),
468 ChildContainer::TypeAliasId(_) => DynMap::default(),
469 ChildContainer::GenericDefId(it) => it.child_by_source(db, file_id),