From bf9ce9e65cea5a79bfba3917c4b8c5ee80f67481 Mon Sep 17 00:00:00 2001 From: Aleksey Kladov Date: Tue, 22 Jun 2021 15:31:04 +0300 Subject: internal: document source_to_def and it's connection to Kotlin&Roslyn --- crates/hir/src/semantics/source_to_def.rs | 69 +++++++++++++++++++++++++++++++ 1 file changed, 69 insertions(+) (limited to 'crates/hir') 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 @@ //! Maps *syntax* of various definitions to their semantic ids. +//! +//! This is a very interesting module, and, in some sense, can be considered a +//! heart of the IDE parts of rust-analyzer. +//! +//! This module solves the following problem: +//! +//! Given a piece of syntax, find the corresponding semantic definition (def). +//! +//! This problem is a part of more-or-less every IDE feature implemented. Every +//! IDE functionality (like goto to definition), conceptually starts with a +//! specific cursor position in a file. Starting with this text offset, we first +//! figure out what syntactic construct are we at: is this a pattern, an +//! expression, an item definition. +//! +//! Knowing only the syntax gives us relatively little info. For example, +//! looking at the syntax of the function we can realise that it is a part of an +//! `impl` block, but we won't be able to tell what trait function the current +//! function overrides, and whether it does that correctly. For that, we need to +//! go from [`ast::Fn`] to [`crate::Function], and that's exactly what this +//! module does. +//! +//! As syntax trees are values and don't know their place of origin/identity, +//! this module also requires [`InFile`] wrappers to understand which specific +//! real or macro-expanded file the tree comes from. +//! +//! The actual algorithm to resolve syntax to def is curious in two aspects: +//! +//! * It is recursive +//! * It uses the inverse algorithm (what is the syntax for this def?) +//! +//! Specifically, the algorithm goes like this: +//! +//! 1. Find the syntactic container for the syntax. For example, field's +//! container is the struct, and structs container is a module. +//! 2. Recursively get the def corresponding to container. +//! 3. Ask the container def for all child defs. These child defs contain +//! the answer and answer's siblings. +//! 4. For each child def, ask for it's source. +//! 5. The child def whose source is the syntax node we've started with +//! is the answer. +//! +//! It's interesting that both Roslyn and Kotlin contain very similar code +//! shape. +//! +//! Let's take a look at Roslyn: +//! +//! +//! +//! +//! The `GetDeclaredType` takes `Syntax` as input, and returns `Symbol` as +//! output. First, it retrieves a `Symbol` for parent `Syntax`: +//! +//! * https://sourceroslyn.io/#Microsoft.CodeAnalysis.CSharp/Compilation/SyntaxTreeSemanticModel.cs,1423 +//! +//! Then, it iterates parent symbol's children, looking for one which has the +//! same text span as the original node: +//! +//! +//! +//! Now, let's look at Kotlin: +//! +//! +//! +//! This function starts with a syntax node (`KtExpression` is syntax, like all +//! `Kt` nodes), and returns a def. It uses +//! `getNonLocalContainingOrThisDeclaration` to get syntactic container for a +//! current node. Then, `findSourceNonLocalFirDeclaration` gets `Fir` for this +//! parent. Finally, `findElementIn` function traverses `Fir` children to find +//! one with the same source we originally started with. use base_db::FileId; use hir_def::{ -- cgit v1.2.3