aboutsummaryrefslogtreecommitdiff
path: root/crates/hir
diff options
context:
space:
mode:
Diffstat (limited to 'crates/hir')
-rw-r--r--crates/hir/src/semantics/source_to_def.rs69
1 files changed, 69 insertions, 0 deletions
diff --git a/crates/hir/src/semantics/source_to_def.rs b/crates/hir/src/semantics/source_to_def.rs
index e8c2ed48e..24afcfba0 100644
--- a/crates/hir/src/semantics/source_to_def.rs
+++ b/crates/hir/src/semantics/source_to_def.rs
@@ -1,4 +1,73 @@
1//! Maps *syntax* of various definitions to their semantic ids. 1//! Maps *syntax* of various definitions to their semantic ids.
2//!
3//! This is a very interesting module, and, in some sense, can be considered a
4//! heart of the IDE parts of rust-analyzer.
5//!
6//! This module solves the following problem:
7//!
8//! Given a piece of syntax, find the corresponding semantic definition (def).
9//!
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.
15//!
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
21//! module does.
22//!
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.
26//!
27//! The actual algorithm to resolve syntax to def is curious in two aspects:
28//!
29//! * It is recursive
30//! * It uses the inverse algorithm (what is the syntax for this def?)
31//!
32//! Specifically, the algorithm goes like this:
33//!
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
41//! is the answer.
42//!
43//! It's interesting that both Roslyn and Kotlin contain very similar code
44//! shape.
45//!
46//! Let's take a look at Roslyn:
47//!
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>
50//!
51//! The `GetDeclaredType` takes `Syntax` as input, and returns `Symbol` as
52//! output. First, it retrieves a `Symbol` for parent `Syntax`:
53//!
54//! * https://sourceroslyn.io/#Microsoft.CodeAnalysis.CSharp/Compilation/SyntaxTreeSemanticModel.cs,1423
55//!
56//! Then, it iterates parent symbol's children, looking for one which has the
57//! same text span as the original node:
58//!
59//! <https://sourceroslyn.io/#Microsoft.CodeAnalysis.CSharp/Compilation/SyntaxTreeSemanticModel.cs,1786>
60//!
61//! Now, let's look at Kotlin:
62//!
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>
64//!
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.
2 71
3use base_db::FileId; 72use base_db::FileId;
4use hir_def::{ 73use hir_def::{