crates/hir/src/semantics/source_to_def.rs

   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.
  71
  72 use base_db::FileId;
  73 use hir_def::{
  74     child_by_source::ChildBySource,
  75     dyn_map::DynMap,
  76     expr::{LabelId, PatId},
  77     keys::{self, Key},
  78     ConstId, ConstParamId, DefWithBodyId, EnumId, EnumVariantId, FieldId, FunctionId, GenericDefId,
  79     ImplId, LifetimeParamId, ModuleId, StaticId, StructId, TraitId, TypeAliasId, TypeParamId,
  80     UnionId, VariantId,
  81 };
  82 use hir_expand::{name::AsName, AstId, MacroCallId, MacroDefKind};
  83 use rustc_hash::FxHashMap;
  84 use smallvec::SmallVec;
  85 use stdx::impl_from;
  86 use syntax::{
  87     ast::{self, NameOwner},
  88     match_ast, AstNode, SyntaxNode,
  89 };
  90
  91 use crate::{db::HirDatabase, InFile, MacroDefId};
  92
  93 pub(super) type SourceToDefCache = FxHashMap<ChildContainer, DynMap>;
  94
  95 pub(super) struct SourceToDefCtx<'a, 'b> {
  96     pub(super) db: &'b dyn HirDatabase,
  97     pub(super) cache: &'a mut SourceToDefCache,
  98 }
  99
 100 impl SourceToDefCtx<'_, '_> {
 101     pub(super) fn file_to_def(&mut self, file: FileId) -> SmallVec<[ModuleId; 1]> {
 102         let _p = profile::span("SourceBinder::to_module_def");
 103         let mut mods = SmallVec::new();
 104         for &crate_id in self.db.relevant_crates(file).iter() {
 105             // FIXME: inner items
 106             let crate_def_map = self.db.crate_def_map(crate_id);
 107             mods.extend(
 108                 crate_def_map
 109                     .modules_for_file(file)
 110                     .map(|local_id| crate_def_map.module_id(local_id)),
 111             )
 112         }
 113         mods
 114     }
 115
 116     pub(super) fn module_to_def(&mut self, src: InFile<ast::Module>) -> Option<ModuleId> {
 117         let _p = profile::span("module_to_def");
 118         let parent_declaration = src
 119             .as_ref()
 120             .map(|it| it.syntax())
 121             .cloned()
 122             .ancestors_with_macros(self.db.upcast())
 123             .skip(1)
 124             .find_map(|it| {
 125                 let m = ast::Module::cast(it.value.clone())?;
 126                 Some(it.with_value(m))
 127             });
 128
 129         let parent_module = match parent_declaration {
 130             Some(parent_declaration) => self.module_to_def(parent_declaration),
 131             None => {
 132                 let file_id = src.file_id.original_file(self.db.upcast());
 133                 self.file_to_def(file_id).get(0).copied()
 134             }
 135         }?;
 136
 137         let child_name = src.value.name()?.as_name();
 138         let def_map = parent_module.def_map(self.db.upcast());
 139         let child_id = *def_map[parent_module.local_id].children.get(&child_name)?;
 140         Some(def_map.module_id(child_id))
 141     }
 142
 143     pub(super) fn source_file_to_def(&mut self, src: InFile<ast::SourceFile>) -> Option<ModuleId> {
 144         let _p = profile::span("source_file_to_def");
 145         let file_id = src.file_id.original_file(self.db.upcast());
 146         self.file_to_def(file_id).get(0).copied()
 147     }
 148
 149     pub(super) fn trait_to_def(&mut self, src: InFile<ast::Trait>) -> Option<TraitId> {
 150         self.to_def(src, keys::TRAIT)
 151     }
 152     pub(super) fn impl_to_def(&mut self, src: InFile<ast::Impl>) -> Option<ImplId> {
 153         self.to_def(src, keys::IMPL)
 154     }
 155     pub(super) fn fn_to_def(&mut self, src: InFile<ast::Fn>) -> Option<FunctionId> {
 156         self.to_def(src, keys::FUNCTION)
 157     }
 158     pub(super) fn struct_to_def(&mut self, src: InFile<ast::Struct>) -> Option<StructId> {
 159         self.to_def(src, keys::STRUCT)
 160     }
 161     pub(super) fn enum_to_def(&mut self, src: InFile<ast::Enum>) -> Option<EnumId> {
 162         self.to_def(src, keys::ENUM)
 163     }
 164     pub(super) fn union_to_def(&mut self, src: InFile<ast::Union>) -> Option<UnionId> {
 165         self.to_def(src, keys::UNION)
 166     }
 167     pub(super) fn static_to_def(&mut self, src: InFile<ast::Static>) -> Option<StaticId> {
 168         self.to_def(src, keys::STATIC)
 169     }
 170     pub(super) fn const_to_def(&mut self, src: InFile<ast::Const>) -> Option<ConstId> {
 171         self.to_def(src, keys::CONST)
 172     }
 173     pub(super) fn type_alias_to_def(&mut self, src: InFile<ast::TypeAlias>) -> Option<TypeAliasId> {
 174         self.to_def(src, keys::TYPE_ALIAS)
 175     }
 176     pub(super) fn record_field_to_def(&mut self, src: InFile<ast::RecordField>) -> Option<FieldId> {
 177         self.to_def(src, keys::RECORD_FIELD)
 178     }
 179     pub(super) fn tuple_field_to_def(&mut self, src: InFile<ast::TupleField>) -> Option<FieldId> {
 180         self.to_def(src, keys::TUPLE_FIELD)
 181     }
 182     pub(super) fn enum_variant_to_def(
 183         &mut self,
 184         src: InFile<ast::Variant>,
 185     ) -> Option<EnumVariantId> {
 186         self.to_def(src, keys::VARIANT)
 187     }
 188     pub(super) fn bind_pat_to_def(
 189         &mut self,
 190         src: InFile<ast::IdentPat>,
 191     ) -> Option<(DefWithBodyId, PatId)> {
 192         let container = self.find_pat_or_label_container(src.as_ref().map(|it| it.syntax()))?;
 193         let (_body, source_map) = self.db.body_with_source_map(container);
 194         let src = src.map(ast::Pat::from);
 195         let pat_id = source_map.node_pat(src.as_ref())?;
 196         Some((container, pat_id))
 197     }
 198     pub(super) fn self_param_to_def(
 199         &mut self,
 200         src: InFile<ast::SelfParam>,
 201     ) -> Option<(DefWithBodyId, PatId)> {
 202         let container = self.find_pat_or_label_container(src.as_ref().map(|it| it.syntax()))?;
 203         let (_body, source_map) = self.db.body_with_source_map(container);
 204         let pat_id = source_map.node_self_param(src.as_ref())?;
 205         Some((container, pat_id))
 206     }
 207     pub(super) fn label_to_def(
 208         &mut self,
 209         src: InFile<ast::Label>,
 210     ) -> Option<(DefWithBodyId, LabelId)> {
 211         let container = self.find_pat_or_label_container(src.as_ref().map(|it| it.syntax()))?;
 212         let (_body, source_map) = self.db.body_with_source_map(container);
 213         let label_id = source_map.node_label(src.as_ref())?;
 214         Some((container, label_id))
 215     }
 216
 217     pub(super) fn item_to_macro_call(&mut self, src: InFile<ast::Item>) -> Option<MacroCallId> {
 218         let map = self.dyn_map(src.as_ref())?;
 219         map[keys::ATTR_MACRO].get(&src).copied()
 220     }
 221
 222     fn to_def<Ast: AstNode + 'static, ID: Copy + 'static>(
 223         &mut self,
 224         src: InFile<Ast>,
 225         key: Key<Ast, ID>,
 226     ) -> Option<ID> {
 227         self.dyn_map(src.as_ref())?[key].get(&src).copied()
 228     }
 229
 230     fn dyn_map<Ast: AstNode + 'static>(&mut self, src: InFile<&Ast>) -> Option<&DynMap> {
 231         let container = self.find_container(src.map(|it| it.syntax()))?;
 232         let db = self.db;
 233         let dyn_map =
 234             &*self.cache.entry(container).or_insert_with(|| container.child_by_source(db));
 235         Some(dyn_map)
 236     }
 237
 238     pub(super) fn type_param_to_def(&mut self, src: InFile<ast::TypeParam>) -> Option<TypeParamId> {
 239         let container: ChildContainer =
 240             self.find_generic_param_container(src.as_ref().map(|it| it.syntax()))?.into();
 241         let db = self.db;
 242         let dyn_map =
 243             &*self.cache.entry(container).or_insert_with(|| container.child_by_source(db));
 244         dyn_map[keys::TYPE_PARAM].get(&src).copied()
 245     }
 246
 247     pub(super) fn lifetime_param_to_def(
 248         &mut self,
 249         src: InFile<ast::LifetimeParam>,
 250     ) -> Option<LifetimeParamId> {
 251         let container: ChildContainer =
 252             self.find_generic_param_container(src.as_ref().map(|it| it.syntax()))?.into();
 253         let db = self.db;
 254         let dyn_map =
 255             &*self.cache.entry(container).or_insert_with(|| container.child_by_source(db));
 256         dyn_map[keys::LIFETIME_PARAM].get(&src).copied()
 257     }
 258
 259     pub(super) fn const_param_to_def(
 260         &mut self,
 261         src: InFile<ast::ConstParam>,
 262     ) -> Option<ConstParamId> {
 263         let container: ChildContainer =
 264             self.find_generic_param_container(src.as_ref().map(|it| it.syntax()))?.into();
 265         let db = self.db;
 266         let dyn_map =
 267             &*self.cache.entry(container).or_insert_with(|| container.child_by_source(db));
 268         dyn_map[keys::CONST_PARAM].get(&src).copied()
 269     }
 270
 271     // FIXME: use DynMap as well?
 272     pub(super) fn macro_to_def(&mut self, src: InFile<ast::Macro>) -> Option<MacroDefId> {
 273         let file_ast_id = self.db.ast_id_map(src.file_id).ast_id(&src.value);
 274         let ast_id = AstId::new(src.file_id, file_ast_id.upcast());
 275         let kind = MacroDefKind::Declarative(ast_id);
 276         let file_id = src.file_id.original_file(self.db.upcast());
 277         let krate = self.file_to_def(file_id).get(0).copied()?.krate();
 278         Some(MacroDefId { krate, kind, local_inner: false })
 279     }
 280
 281     pub(super) fn find_container(&mut self, src: InFile<&SyntaxNode>) -> Option<ChildContainer> {
 282         for container in src.cloned().ancestors_with_macros(self.db.upcast()).skip(1) {
 283             if let Some(res) = self.container_to_def(container) {
 284                 return Some(res);
 285             }
 286         }
 287
 288         let def = self.file_to_def(src.file_id.original_file(self.db.upcast())).get(0).copied()?;
 289         Some(def.into())
 290     }
 291
 292     fn container_to_def(&mut self, container: InFile<SyntaxNode>) -> Option<ChildContainer> {
 293         let cont = match_ast! {
 294             match (container.value) {
 295                 ast::Module(it) => {
 296                     let def = self.module_to_def(container.with_value(it))?;
 297                     def.into()
 298                 },
 299                 ast::Trait(it) => {
 300                     let def = self.trait_to_def(container.with_value(it))?;
 301                     def.into()
 302                 },
 303                 ast::Impl(it) => {
 304                     let def = self.impl_to_def(container.with_value(it))?;
 305                     def.into()
 306                 },
 307                 ast::Fn(it) => {
 308                     let def = self.fn_to_def(container.with_value(it))?;
 309                     DefWithBodyId::from(def).into()
 310                 },
 311                 ast::Struct(it) => {
 312                     let def = self.struct_to_def(container.with_value(it))?;
 313                     VariantId::from(def).into()
 314                 },
 315                 ast::Enum(it) => {
 316                     let def = self.enum_to_def(container.with_value(it))?;
 317                     def.into()
 318                 },
 319                 ast::Union(it) => {
 320                     let def = self.union_to_def(container.with_value(it))?;
 321                     VariantId::from(def).into()
 322                 },
 323                 ast::Static(it) => {
 324                     let def = self.static_to_def(container.with_value(it))?;
 325                     DefWithBodyId::from(def).into()
 326                 },
 327                 ast::Const(it) => {
 328                     let def = self.const_to_def(container.with_value(it))?;
 329                     DefWithBodyId::from(def).into()
 330                 },
 331                 ast::TypeAlias(it) => {
 332                     let def = self.type_alias_to_def(container.with_value(it))?;
 333                     def.into()
 334                 },
 335                 ast::Variant(it) => {
 336                     let def = self.enum_variant_to_def(container.with_value(it))?;
 337                     VariantId::from(def).into()
 338                 },
 339                 _ => return None,
 340             }
 341         };
 342         Some(cont)
 343     }
 344
 345     fn find_generic_param_container(&mut self, src: InFile<&SyntaxNode>) -> Option<GenericDefId> {
 346         for container in src.cloned().ancestors_with_macros(self.db.upcast()).skip(1) {
 347             let res: GenericDefId = match_ast! {
 348                 match (container.value) {
 349                     ast::Fn(it) => self.fn_to_def(container.with_value(it))?.into(),
 350                     ast::Struct(it) => self.struct_to_def(container.with_value(it))?.into(),
 351                     ast::Enum(it) => self.enum_to_def(container.with_value(it))?.into(),
 352                     ast::Trait(it) => self.trait_to_def(container.with_value(it))?.into(),
 353                     ast::TypeAlias(it) => self.type_alias_to_def(container.with_value(it))?.into(),
 354                     ast::Impl(it) => self.impl_to_def(container.with_value(it))?.into(),
 355                     _ => continue,
 356                 }
 357             };
 358             return Some(res);
 359         }
 360         None
 361     }
 362
 363     fn find_pat_or_label_container(&mut self, src: InFile<&SyntaxNode>) -> Option<DefWithBodyId> {
 364         for container in src.cloned().ancestors_with_macros(self.db.upcast()).skip(1) {
 365             let res: DefWithBodyId = match_ast! {
 366                 match (container.value) {
 367                     ast::Const(it) => self.const_to_def(container.with_value(it))?.into(),
 368                     ast::Static(it) => self.static_to_def(container.with_value(it))?.into(),
 369                     ast::Fn(it) => self.fn_to_def(container.with_value(it))?.into(),
 370                     _ => continue,
 371                 }
 372             };
 373             return Some(res);
 374         }
 375         None
 376     }
 377 }
 378
 379 #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
 380 pub(crate) enum ChildContainer {
 381     DefWithBodyId(DefWithBodyId),
 382     ModuleId(ModuleId),
 383     TraitId(TraitId),
 384     ImplId(ImplId),
 385     EnumId(EnumId),
 386     VariantId(VariantId),
 387     TypeAliasId(TypeAliasId),
 388     /// XXX: this might be the same def as, for example an `EnumId`. However,
 389     /// here the children are generic parameters, and not, eg enum variants.
 390     GenericDefId(GenericDefId),
 391 }
 392 impl_from! {
 393     DefWithBodyId,
 394     ModuleId,
 395     TraitId,
 396     ImplId,
 397     EnumId,
 398     VariantId,
 399     TypeAliasId,
 400     GenericDefId
 401     for ChildContainer
 402 }
 403
 404 impl ChildContainer {
 405     fn child_by_source(self, db: &dyn HirDatabase) -> DynMap {
 406         let db = db.upcast();
 407         match self {
 408             ChildContainer::DefWithBodyId(it) => it.child_by_source(db),
 409             ChildContainer::ModuleId(it) => it.child_by_source(db),
 410             ChildContainer::TraitId(it) => it.child_by_source(db),
 411             ChildContainer::ImplId(it) => it.child_by_source(db),
 412             ChildContainer::EnumId(it) => it.child_by_source(db),
 413             ChildContainer::VariantId(it) => it.child_by_source(db),
 414             ChildContainer::TypeAliasId(_) => DynMap::default(),
 415             ChildContainer::GenericDefId(it) => it.child_by_source(db),
 416         }
 417     }
 418 }