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