Merge #2837

2837: Accidentally quadratic r=matklad a=matklad

Our syntax highlighting is accdentally quadratic. Current state of the PR fixes it in a pretty crude way, looks like for the proper fix we need to redo how source-analyzer works. 

**NB:** don't be scared by diff stats, that's mostly a test-data file

Co-authored-by: Aleksey Kladov <[email protected]>

3 files changed, 217 insertions, 98 deletions

diff --git a/crates/ra_hir/src/lib.rs b/crates/ra_hir/src/lib.rs
index a1cf89010..a2350573c 100644
--- a/crates/ra_hir/src/lib.rs
+++ b/crates/ra_hir/src/lib.rs
@@ -8,7 +8,7 @@
 #![recursion_limit = "512"]
 
 macro_rules! impl_froms {
-    ($e:ident: $($v:ident $(($($sv:ident),*))?),*) => {
+    ($e:ident: $($v:ident $(($($sv:ident),*))?),*$(,)?) => {
         $(
             impl From<$v> for $e {
                 fn from(it: $v) -> $e {
@@ -28,6 +28,7 @@ macro_rules! impl_froms {
 
 pub mod db;
 pub mod source_analyzer;
+pub mod source_binder;
 
 pub mod diagnostics;
 
@@ -47,6 +48,7 @@ pub use crate::{
     from_source::FromSource,
     has_source::HasSource,
     source_analyzer::{PathResolution, ScopeEntryWithSyntax, SourceAnalyzer},
+    source_binder::SourceBinder,
 };
 
 pub use hir_def::{
diff --git a/crates/ra_hir/src/source_analyzer.rs b/crates/ra_hir/src/source_analyzer.rs
index 76e0bff34..4f8fc9602 100644
--- a/crates/ra_hir/src/source_analyzer.rs
+++ b/crates/ra_hir/src/source_analyzer.rs
@@ -14,26 +14,22 @@ use hir_def::{
         BodySourceMap,
     },
     expr::{ExprId, PatId},
-    nameres::ModuleSource,
-    resolver::{self, resolver_for_scope, HasResolver, Resolver, TypeNs, ValueNs},
+    resolver::{self, resolver_for_scope, Resolver, TypeNs, ValueNs},
     DefWithBodyId, TraitId,
 };
 use hir_expand::{
     hygiene::Hygiene, name::AsName, AstId, HirFileId, InFile, MacroCallId, MacroCallKind,
 };
 use hir_ty::{InEnvironment, InferenceResult, TraitEnvironment};
-use ra_prof::profile;
 use ra_syntax::{
     ast::{self, AstNode},
-    match_ast, AstPtr,
-    SyntaxKind::*,
-    SyntaxNode, SyntaxNodePtr, SyntaxToken, TextRange, TextUnit,
+    AstPtr, SyntaxNode, SyntaxNodePtr, SyntaxToken, TextRange, TextUnit,
 };
 use rustc_hash::FxHashSet;
 
 use crate::{
-    db::HirDatabase, Adt, Const, DefWithBody, Enum, EnumVariant, FromSource, Function, ImplBlock,
-    Local, MacroDef, Name, Path, ScopeDef, Static, Struct, Trait, Type, TypeAlias, TypeParam,
+    db::HirDatabase, Adt, Const, DefWithBody, EnumVariant, Function, Local, MacroDef, Name, Path,
+    ScopeDef, Static, Struct, Trait, Type, TypeAlias, TypeParam,
 };
 
 /// `SourceAnalyzer` is a convenience wrapper which exposes HIR API in terms of
@@ -109,37 +105,43 @@ impl SourceAnalyzer {
         node: InFile<&SyntaxNode>,
         offset: Option<TextUnit>,
     ) -> SourceAnalyzer {
-        let _p = profile("SourceAnalyzer::new");
-        let def_with_body = def_with_body_from_child_node(db, node);
-        if let Some(def) = def_with_body {
-            let (_body, source_map) = db.body_with_source_map(def.into());
-            let scopes = db.expr_scopes(def.into());
-            let scope = match offset {
-                None => scope_for(&scopes, &source_map, node),
-                Some(offset) => scope_for_offset(&scopes, &source_map, node.with_value(offset)),
-            };
-            let resolver = resolver_for_scope(db, def.into(), scope);
-            SourceAnalyzer {
-                resolver,
-                body_owner: Some(def),
-                body_source_map: Some(source_map),
-                infer: Some(db.infer(def.into())),
-                scopes: Some(scopes),
-                file_id: node.file_id,
-            }
-        } else {
-            SourceAnalyzer {
-                resolver: node
-                    .value
-                    .ancestors()
-                    .find_map(|it| try_get_resolver_for_node(db, node.with_value(&it)))
-                    .unwrap_or_default(),
-                body_owner: None,
-                body_source_map: None,
-                infer: None,
-                scopes: None,
-                file_id: node.file_id,
-            }
+        crate::source_binder::SourceBinder::new(db).analyze(node, offset)
+    }
+
+    pub(crate) fn new_for_body(
+        db: &impl HirDatabase,
+        def: DefWithBodyId,
+        node: InFile<&SyntaxNode>,
+        offset: Option<TextUnit>,
+    ) -> SourceAnalyzer {
+        let (_body, source_map) = db.body_with_source_map(def);
+        let scopes = db.expr_scopes(def);
+        let scope = match offset {
+            None => scope_for(&scopes, &source_map, node),
+            Some(offset) => scope_for_offset(&scopes, &source_map, node.with_value(offset)),
+        };
+        let resolver = resolver_for_scope(db, def, scope);
+        SourceAnalyzer {
+            resolver,
+            body_owner: Some(def.into()),
+            body_source_map: Some(source_map),
+            infer: Some(db.infer(def)),
+            scopes: Some(scopes),
+            file_id: node.file_id,
+        }
+    }
+
+    pub(crate) fn new_for_resolver(
+        resolver: Resolver,
+        node: InFile<&SyntaxNode>,
+    ) -> SourceAnalyzer {
+        SourceAnalyzer {
+            resolver,
+            body_owner: None,
+            body_source_map: None,
+            infer: None,
+            scopes: None,
+            file_id: node.file_id,
         }
     }
 
@@ -366,64 +368,6 @@ impl SourceAnalyzer {
     }
 }
 
-fn try_get_resolver_for_node(db: &impl HirDatabase, node: InFile<&SyntaxNode>) -> Option<Resolver> {
-    match_ast! {
-        match (node.value) {
-            ast::Module(it) => {
-                let src = node.with_value(it);
-                Some(crate::Module::from_declaration(db, src)?.id.resolver(db))
-            },
-             ast::SourceFile(it) => {
-                let src = node.with_value(ModuleSource::SourceFile(it));
-                Some(crate::Module::from_definition(db, src)?.id.resolver(db))
-            },
-            ast::StructDef(it) => {
-                let src = node.with_value(it);
-                Some(Struct::from_source(db, src)?.id.resolver(db))
-            },
-            ast::EnumDef(it) => {
-                let src = node.with_value(it);
-                Some(Enum::from_source(db, src)?.id.resolver(db))
-            },
-            ast::ImplBlock(it) => {
-                let src = node.with_value(it);
-                Some(ImplBlock::from_source(db, src)?.id.resolver(db))
-            },
-            ast::TraitDef(it) => {
-                let src = node.with_value(it);
-                Some(Trait::from_source(db, src)?.id.resolver(db))
-            },
-            _ => match node.value.kind() {
-                FN_DEF | CONST_DEF | STATIC_DEF => {
-                    let def = def_with_body_from_child_node(db, node)?;
-                    let def = DefWithBodyId::from(def);
-                    Some(def.resolver(db))
-                }
-                // FIXME add missing cases
-                _ => None
-            }
-        }
-    }
-}
-
-fn def_with_body_from_child_node(
-    db: &impl HirDatabase,
-    child: InFile<&SyntaxNode>,
-) -> Option<DefWithBody> {
-    let _p = profile("def_with_body_from_child_node");
-    child.cloned().ancestors_with_macros(db).find_map(|node| {
-        let n = &node.value;
-        match_ast! {
-            match n {
-                ast::FnDef(def)  => { return Function::from_source(db, node.with_value(def)).map(DefWithBody::from); },
-                ast::ConstDef(def) => { return Const::from_source(db, node.with_value(def)).map(DefWithBody::from); },
-                ast::StaticDef(def) => { return Static::from_source(db, node.with_value(def)).map(DefWithBody::from); },
-                _ => { None },
-            }
-        }
-    })
-}
-
 fn scope_for(
     scopes: &ExprScopes,
     source_map: &BodySourceMap,
diff --git a/crates/ra_hir/src/source_binder.rs b/crates/ra_hir/src/source_binder.rs
new file mode 100644
index 000000000..00541dbe1
--- /dev/null
+++ b/crates/ra_hir/src/source_binder.rs
@@ -0,0 +1,173 @@
+//! `SourceBinder` should be the main entry point for getting info about source code.
+//! It's main task is to map source syntax trees to hir-level IDs.
+//!
+//! It is intended to subsume `FromSource` and `SourceAnalyzer`.
+
+use hir_def::{
+    child_by_source::ChildBySource,
+    dyn_map::DynMap,
+    keys::{self, Key},
+    resolver::{HasResolver, Resolver},
+    ConstId, DefWithBodyId, EnumId, EnumVariantId, FunctionId, ImplId, ModuleId, StaticId,
+    StructFieldId, StructId, TraitId, TypeAliasId, UnionId, VariantId,
+};
+use hir_expand::InFile;
+use ra_prof::profile;
+use ra_syntax::{ast, match_ast, AstNode, SyntaxNode, TextUnit};
+use rustc_hash::FxHashMap;
+
+use crate::{db::HirDatabase, ModuleSource, SourceAnalyzer};
+
+pub struct SourceBinder<'a, DB> {
+    pub db: &'a DB,
+    child_by_source_cache: FxHashMap<ChildContainer, DynMap>,
+}
+
+impl<DB: HirDatabase> SourceBinder<'_, DB> {
+    pub fn new(db: &DB) -> SourceBinder<DB> {
+        SourceBinder { db, child_by_source_cache: FxHashMap::default() }
+    }
+
+    pub fn analyze(
+        &mut self,
+        src: InFile<&SyntaxNode>,
+        offset: Option<TextUnit>,
+    ) -> SourceAnalyzer {
+        let _p = profile("SourceBinder::analyzer");
+        let container = match self.find_container(src) {
+            Some(it) => it,
+            None => return SourceAnalyzer::new_for_resolver(Resolver::default(), src),
+        };
+
+        let resolver = match container {
+            ChildContainer::DefWithBodyId(def) => {
+                return SourceAnalyzer::new_for_body(self.db, def, src, offset)
+            }
+            ChildContainer::TraitId(it) => it.resolver(self.db),
+            ChildContainer::ImplId(it) => it.resolver(self.db),
+            ChildContainer::ModuleId(it) => it.resolver(self.db),
+            ChildContainer::EnumId(it) => it.resolver(self.db),
+            ChildContainer::VariantId(it) => it.resolver(self.db),
+        };
+        SourceAnalyzer::new_for_resolver(resolver, src)
+    }
+
+    pub fn to_def<D, T>(&mut self, src: InFile<T>) -> Option<D>
+    where
+        D: From<T::ID>,
+        T: ToId,
+    {
+        let id: T::ID = self.to_id(src)?;
+        Some(id.into())
+    }
+
+    fn to_id<T: ToId>(&mut self, src: InFile<T>) -> Option<T::ID> {
+        let container = self.find_container(src.as_ref().map(|it| it.syntax()))?;
+        let db = self.db;
+        let dyn_map =
+            &*self.child_by_source_cache.entry(container).or_insert_with(|| match container {
+                ChildContainer::DefWithBodyId(it) => it.child_by_source(db),
+                ChildContainer::ModuleId(it) => it.child_by_source(db),
+                ChildContainer::TraitId(it) => it.child_by_source(db),
+                ChildContainer::ImplId(it) => it.child_by_source(db),
+                ChildContainer::EnumId(it) => it.child_by_source(db),
+                ChildContainer::VariantId(it) => it.child_by_source(db),
+            });
+        dyn_map[T::KEY].get(&src).copied()
+    }
+
+    fn find_container(&mut self, src: InFile<&SyntaxNode>) -> Option<ChildContainer> {
+        for container in src.cloned().ancestors_with_macros(self.db).skip(1) {
+            let res: ChildContainer = match_ast! {
+                match (container.value) {
+                    ast::TraitDef(it) => {
+                        let def: TraitId = self.to_id(container.with_value(it))?;
+                        def.into()
+                    },
+                    ast::ImplBlock(it) => {
+                        let def: ImplId = self.to_id(container.with_value(it))?;
+                        def.into()
+                    },
+                    ast::FnDef(it) => {
+                        let def: FunctionId = self.to_id(container.with_value(it))?;
+                        DefWithBodyId::from(def).into()
+                    },
+                    ast::StaticDef(it) => {
+                        let def: StaticId = self.to_id(container.with_value(it))?;
+                        DefWithBodyId::from(def).into()
+                    },
+                    ast::ConstDef(it) => {
+                        let def: ConstId = self.to_id(container.with_value(it))?;
+                        DefWithBodyId::from(def).into()
+                    },
+                    ast::EnumDef(it) => {
+                        let def: EnumId = self.to_id(container.with_value(it))?;
+                        def.into()
+                    },
+                    ast::StructDef(it) => {
+                        let def: StructId = self.to_id(container.with_value(it))?;
+                        VariantId::from(def).into()
+                    },
+                    ast::UnionDef(it) => {
+                        let def: UnionId = self.to_id(container.with_value(it))?;
+                        VariantId::from(def).into()
+                    },
+                    // FIXME: handle out-of-line modules here
+                    _ => { continue },
+                }
+            };
+            return Some(res);
+        }
+
+        let module_source = ModuleSource::from_child_node(self.db, src);
+        let c = crate::Module::from_definition(self.db, src.with_value(module_source))?;
+        Some(c.id.into())
+    }
+}
+
+#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
+enum ChildContainer {
+    DefWithBodyId(DefWithBodyId),
+    ModuleId(ModuleId),
+    TraitId(TraitId),
+    ImplId(ImplId),
+    EnumId(EnumId),
+    VariantId(VariantId),
+}
+impl_froms! {
+    ChildContainer:
+    DefWithBodyId,
+    ModuleId,
+    TraitId,
+    ImplId,
+    EnumId,
+    VariantId,
+}
+
+pub trait ToId: Sized + AstNode + 'static {
+    type ID: Sized + Copy + 'static;
+    const KEY: Key<Self, Self::ID>;
+}
+
+macro_rules! to_id_impls {
+    ($(($id:ident, $ast:path, $key:path)),* ,) => {$(
+        impl ToId for $ast {
+            type ID = $id;
+            const KEY: Key<Self, Self::ID> = $key;
+        }
+    )*}
+}
+
+to_id_impls![
+    (StructId, ast::StructDef, keys::STRUCT),
+    (UnionId, ast::UnionDef, keys::UNION),
+    (EnumId, ast::EnumDef, keys::ENUM),
+    (TraitId, ast::TraitDef, keys::TRAIT),
+    (FunctionId, ast::FnDef, keys::FUNCTION),
+    (StaticId, ast::StaticDef, keys::STATIC),
+    (ConstId, ast::ConstDef, keys::CONST),
+    (TypeAliasId, ast::TypeAliasDef, keys::TYPE_ALIAS),
+    (ImplId, ast::ImplBlock, keys::IMPL),
+    (StructFieldId, ast::RecordFieldDef, keys::RECORD_FIELD),
+    (EnumVariantId, ast::EnumVariant, keys::ENUM_VARIANT),
+];