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]>

6 files changed, 105 insertions, 72 deletions

diff --git a/crates/ra_ide/src/goto_definition.rs b/crates/ra_ide/src/goto_definition.rs
index 79d332e8c..f2b5af321 100644
--- a/crates/ra_ide/src/goto_definition.rs
+++ b/crates/ra_ide/src/goto_definition.rs
@@ -1,6 +1,6 @@
 //! FIXME: write short doc here
 
-use hir::{db::AstDatabase, InFile};
+use hir::{db::AstDatabase, InFile, SourceBinder};
 use ra_syntax::{
     ast::{self, DocCommentsOwner},
     match_ast, AstNode,
@@ -72,7 +72,8 @@ pub(crate) fn reference_definition(
 ) -> ReferenceResult {
     use self::ReferenceResult::*;
 
-    let name_kind = classify_name_ref(db, name_ref).map(|d| d.kind);
+    let mut sb = SourceBinder::new(db);
+    let name_kind = classify_name_ref(&mut sb, name_ref).map(|d| d.kind);
     match name_kind {
         Some(Macro(it)) => return Exact(it.to_nav(db)),
         Some(Field(it)) => return Exact(it.to_nav(db)),
diff --git a/crates/ra_ide/src/hover.rs b/crates/ra_ide/src/hover.rs
index 5548681f1..6661e5cb2 100644
--- a/crates/ra_ide/src/hover.rs
+++ b/crates/ra_ide/src/hover.rs
@@ -1,6 +1,6 @@
 //! FIXME: write short doc here
 
-use hir::{db::AstDatabase, Adt, HasSource, HirDisplay};
+use hir::{db::AstDatabase, Adt, HasSource, HirDisplay, SourceBinder};
 use ra_db::SourceDatabase;
 use ra_syntax::{
     algo::find_covering_element,
@@ -152,13 +152,14 @@ pub(crate) fn hover(db: &RootDatabase, position: FilePosition) -> Option<RangeIn
 
     let mut res = HoverResult::new();
 
+    let mut sb = SourceBinder::new(db);
     if let Some((range, name_kind)) = match_ast! {
         match (token.value.parent()) {
             ast::NameRef(name_ref) => {
-                classify_name_ref(db, token.with_value(&name_ref)).map(|d| (name_ref.syntax().text_range(), d.kind))
+                classify_name_ref(&mut sb, token.with_value(&name_ref)).map(|d| (name_ref.syntax().text_range(), d.kind))
             },
             ast::Name(name) => {
-                classify_name(db, token.with_value(&name)).map(|d| (name.syntax().text_range(), d.kind))
+                classify_name(&mut sb, token.with_value(&name)).map(|d| (name.syntax().text_range(), d.kind))
             },
             _ => None,
         }
@@ -742,7 +743,7 @@ fn func(foo: i32) { if true { <|>foo; }; }
             }
             fn foo(bar:u32) {
                 let a = id!(ba<|>r);
-            }            
+            }
             ",
             &["u32"],
         );
diff --git a/crates/ra_ide/src/inlay_hints.rs b/crates/ra_ide/src/inlay_hints.rs
index 8cb0c70dd..e2da96129 100644
--- a/crates/ra_ide/src/inlay_hints.rs
+++ b/crates/ra_ide/src/inlay_hints.rs
@@ -1,6 +1,6 @@
 //! FIXME: write short doc here
 
-use hir::{HirDisplay, SourceAnalyzer};
+use hir::{HirDisplay, SourceAnalyzer, SourceBinder};
 use once_cell::unsync::Lazy;
 use ra_prof::profile;
 use ra_syntax::{
@@ -29,22 +29,23 @@ pub(crate) fn inlay_hints(
     file: &SourceFile,
     max_inlay_hint_length: Option<usize>,
 ) -> Vec<InlayHint> {
+    let mut sb = SourceBinder::new(db);
     file.syntax()
         .descendants()
-        .flat_map(|node| get_inlay_hints(db, file_id, &node, max_inlay_hint_length))
+        .flat_map(|node| get_inlay_hints(&mut sb, file_id, &node, max_inlay_hint_length))
         .flatten()
         .collect()
 }
 
 fn get_inlay_hints(
-    db: &RootDatabase,
+    sb: &mut SourceBinder<RootDatabase>,
     file_id: FileId,
     node: &SyntaxNode,
     max_inlay_hint_length: Option<usize>,
 ) -> Option<Vec<InlayHint>> {
     let _p = profile("get_inlay_hints");
-    let analyzer =
-        Lazy::new(|| SourceAnalyzer::new(db, hir::InFile::new(file_id.into(), node), None));
+    let db = sb.db;
+    let analyzer = Lazy::new(move || sb.analyze(hir::InFile::new(file_id.into(), node), None));
     match_ast! {
         match node {
             ast::LetStmt(it) => {
diff --git a/crates/ra_ide/src/references.rs b/crates/ra_ide/src/references.rs
index 2c753dade..5e2fe1905 100644
--- a/crates/ra_ide/src/references.rs
+++ b/crates/ra_ide/src/references.rs
@@ -14,7 +14,7 @@ mod name_definition;
 mod rename;
 mod search_scope;
 
-use hir::InFile;
+use hir::{InFile, SourceBinder};
 use once_cell::unsync::Lazy;
 use ra_db::{SourceDatabase, SourceDatabaseExt};
 use ra_prof::profile;
@@ -171,13 +171,14 @@ fn find_name(
     syntax: &SyntaxNode,
     position: FilePosition,
 ) -> Option<RangeInfo<(String, NameDefinition)>> {
+    let mut sb = SourceBinder::new(db);
     if let Some(name) = find_node_at_offset::<ast::Name>(&syntax, position.offset) {
-        let def = classify_name(db, InFile::new(position.file_id.into(), &name))?;
+        let def = classify_name(&mut sb, InFile::new(position.file_id.into(), &name))?;
         let range = name.syntax().text_range();
         return Some(RangeInfo::new(range, (name.text().to_string(), def)));
     }
     let name_ref = find_node_at_offset::<ast::NameRef>(&syntax, position.offset)?;
-    let def = classify_name_ref(db, InFile::new(position.file_id.into(), &name_ref))?;
+    let def = classify_name_ref(&mut sb, InFile::new(position.file_id.into(), &name_ref))?;
     let range = name_ref.syntax().text_range();
     Some(RangeInfo::new(range, (name_ref.text().to_string(), def)))
 }
@@ -195,7 +196,9 @@ fn process_definition(
 
     for (file_id, search_range) in scope {
         let text = db.file_text(file_id);
+
         let parse = Lazy::new(|| SourceFile::parse(&text));
+        let mut sb = Lazy::new(|| SourceBinder::new(db));
 
         for (idx, _) in text.match_indices(pat) {
             let offset = TextUnit::from_usize(idx);
@@ -209,7 +212,11 @@ fn process_definition(
                         continue;
                     }
                 }
-                if let Some(d) = classify_name_ref(db, InFile::new(file_id.into(), &name_ref)) {
+                // FIXME: reuse sb
+                // See https://github.com/rust-lang/rust/pull/68198#issuecomment-574269098
+
+                if let Some(d) = classify_name_ref(&mut sb, InFile::new(file_id.into(), &name_ref))
+                {
                     if d == def {
                         let kind = if name_ref
                             .syntax()
@@ -309,7 +316,7 @@ mod tests {
     }
     impl Foo {
         fn f() -> i32 { 42 }
-    }    
+    }
     fn main() {
         let f: Foo;
         f = Foo {a: Foo::f()};
@@ -319,7 +326,7 @@ mod tests {
         check_result(
             refs,
             "Foo STRUCT_DEF FileId(1) [5; 39) [12; 15) Other",
-            &["FileId(1) [142; 145) StructLiteral"],
+            &["FileId(1) [138; 141) StructLiteral"],
         );
     }
 
diff --git a/crates/ra_ide/src/references/classify.rs b/crates/ra_ide/src/references/classify.rs
index 3483a7176..4a6e11e27 100644
--- a/crates/ra_ide/src/references/classify.rs
+++ b/crates/ra_ide/src/references/classify.rs
@@ -1,6 +1,6 @@
 //! Functions that are used to classify an element from its definition or reference.
 
-use hir::{FromSource, InFile, Module, ModuleSource, PathResolution, SourceAnalyzer};
+use hir::{FromSource, InFile, Module, ModuleSource, PathResolution, SourceBinder};
 use ra_prof::profile;
 use ra_syntax::{ast, match_ast, AstNode};
 use test_utils::tested_by;
@@ -11,7 +11,10 @@ use super::{
 };
 use crate::db::RootDatabase;
 
-pub(crate) fn classify_name(db: &RootDatabase, name: InFile<&ast::Name>) -> Option<NameDefinition> {
+pub(crate) fn classify_name(
+    sb: &mut SourceBinder<RootDatabase>,
+    name: InFile<&ast::Name>,
+) -> Option<NameDefinition> {
     let _p = profile("classify_name");
     let parent = name.value.syntax().parent()?;
 
@@ -19,90 +22,89 @@ pub(crate) fn classify_name(db: &RootDatabase, name: InFile<&ast::Name>) -> Opti
         match parent {
             ast::BindPat(it) => {
                 let src = name.with_value(it);
-                let local = hir::Local::from_source(db, src)?;
+                let local = hir::Local::from_source(sb.db, src)?;
                 Some(NameDefinition {
                     visibility: None,
-                    container: local.module(db),
+                    container: local.module(sb.db),
                     kind: NameKind::Local(local),
                 })
             },
             ast::RecordFieldDef(it) => {
-                let ast = hir::FieldSource::Named(it);
-                let src = name.with_value(ast);
-                let field = hir::StructField::from_source(db, src)?;
-                Some(from_struct_field(db, field))
+                let src = name.with_value(it);
+                let field: hir::StructField = sb.to_def(src)?;
+                Some(from_struct_field(sb.db, field))
             },
             ast::Module(it) => {
                 let def = {
                     if !it.has_semi() {
                         let ast = hir::ModuleSource::Module(it);
                         let src = name.with_value(ast);
-                        hir::Module::from_definition(db, src)
+                        hir::Module::from_definition(sb.db, src)
                     } else {
                         let src = name.with_value(it);
-                        hir::Module::from_declaration(db, src)
+                        hir::Module::from_declaration(sb.db, src)
                     }
                 }?;
-                Some(from_module_def(db, def.into(), None))
+                Some(from_module_def(sb.db, def.into(), None))
             },
             ast::StructDef(it) => {
                 let src = name.with_value(it);
-                let def = hir::Struct::from_source(db, src)?;
-                Some(from_module_def(db, def.into(), None))
+                let def: hir::Struct = sb.to_def(src)?;
+                Some(from_module_def(sb.db, def.into(), None))
             },
             ast::EnumDef(it) => {
                 let src = name.with_value(it);
-                let def = hir::Enum::from_source(db, src)?;
-                Some(from_module_def(db, def.into(), None))
+                let def: hir::Enum = sb.to_def(src)?;
+                Some(from_module_def(sb.db, def.into(), None))
             },
             ast::TraitDef(it) => {
                 let src = name.with_value(it);
-                let def = hir::Trait::from_source(db, src)?;
-                Some(from_module_def(db, def.into(), None))
+                let def: hir::Trait = sb.to_def(src)?;
+                Some(from_module_def(sb.db, def.into(), None))
             },
             ast::StaticDef(it) => {
                 let src = name.with_value(it);
-                let def = hir::Static::from_source(db, src)?;
-                Some(from_module_def(db, def.into(), None))
+                let def: hir::Static = sb.to_def(src)?;
+                Some(from_module_def(sb.db, def.into(), None))
             },
             ast::EnumVariant(it) => {
                 let src = name.with_value(it);
-                let def = hir::EnumVariant::from_source(db, src)?;
-                Some(from_module_def(db, def.into(), None))
+                let def: hir::EnumVariant = sb.to_def(src)?;
+                Some(from_module_def(sb.db, def.into(), None))
             },
             ast::FnDef(it) => {
                 let src = name.with_value(it);
-                let def = hir::Function::from_source(db, src)?;
+                let def: hir::Function = sb.to_def(src)?;
                 if parent.parent().and_then(ast::ItemList::cast).is_some() {
-                    Some(from_assoc_item(db, def.into()))
+                    Some(from_assoc_item(sb.db, def.into()))
                 } else {
-                    Some(from_module_def(db, def.into(), None))
+                    Some(from_module_def(sb.db, def.into(), None))
                 }
             },
             ast::ConstDef(it) => {
                 let src = name.with_value(it);
-                let def = hir::Const::from_source(db, src)?;
+                let def: hir::Const = sb.to_def(src)?;
                 if parent.parent().and_then(ast::ItemList::cast).is_some() {
-                    Some(from_assoc_item(db, def.into()))
+                    Some(from_assoc_item(sb.db, def.into()))
                 } else {
-                    Some(from_module_def(db, def.into(), None))
+                    Some(from_module_def(sb.db, def.into(), None))
                 }
             },
             ast::TypeAliasDef(it) => {
                 let src = name.with_value(it);
-                let def = hir::TypeAlias::from_source(db, src)?;
+                let def: hir::TypeAlias = sb.to_def(src)?;
                 if parent.parent().and_then(ast::ItemList::cast).is_some() {
-                    Some(from_assoc_item(db, def.into()))
+                    Some(from_assoc_item(sb.db, def.into()))
                 } else {
-                    Some(from_module_def(db, def.into(), None))
+                    Some(from_module_def(sb.db, def.into(), None))
                 }
             },
             ast::MacroCall(it) => {
                 let src = name.with_value(it);
-                let def = hir::MacroDef::from_source(db, src.clone())?;
+                let def = hir::MacroDef::from_source(sb.db, src.clone())?;
 
-                let module_src = ModuleSource::from_child_node(db, src.as_ref().map(|it| it.syntax()));
-                let module = Module::from_definition(db, src.with_value(module_src))?;
+                let module_src = ModuleSource::from_child_node(sb.db, src.as_ref().map(|it| it.syntax()));
+                let module = Module::from_definition(sb.db, src.with_value(module_src))?;
 
                 Some(NameDefinition {
                     visibility: None,
@@ -112,10 +114,10 @@ pub(crate) fn classify_name(db: &RootDatabase, name: InFile<&ast::Name>) -> Opti
             },
             ast::TypeParam(it) => {
                 let src = name.with_value(it);
-                let def = hir::TypeParam::from_source(db, src)?;
+                let def = hir::TypeParam::from_source(sb.db, src)?;
                 Some(NameDefinition {
                     visibility: None,
-                    container: def.module(db),
+                    container: def.module(sb.db),
                     kind: NameKind::TypeParam(def),
                 })
             },
@@ -125,25 +127,25 @@ pub(crate) fn classify_name(db: &RootDatabase, name: InFile<&ast::Name>) -> Opti
 }
 
 pub(crate) fn classify_name_ref(
-    db: &RootDatabase,
+    sb: &mut SourceBinder<RootDatabase>,
     name_ref: InFile<&ast::NameRef>,
 ) -> Option<NameDefinition> {
     let _p = profile("classify_name_ref");
 
     let parent = name_ref.value.syntax().parent()?;
-    let analyzer = SourceAnalyzer::new(db, name_ref.map(|it| it.syntax()), None);
+    let analyzer = sb.analyze(name_ref.map(|it| it.syntax()), None);
 
     if let Some(method_call) = ast::MethodCallExpr::cast(parent.clone()) {
         tested_by!(goto_def_for_methods);
         if let Some(func) = analyzer.resolve_method_call(&method_call) {
-            return Some(from_assoc_item(db, func.into()));
+            return Some(from_assoc_item(sb.db, func.into()));
         }
     }
 
     if let Some(field_expr) = ast::FieldExpr::cast(parent.clone()) {
         tested_by!(goto_def_for_fields);
         if let Some(field) = analyzer.resolve_field(&field_expr) {
-            return Some(from_struct_field(db, field));
+            return Some(from_struct_field(sb.db, field));
         }
     }
 
@@ -151,30 +153,32 @@ pub(crate) fn classify_name_ref(
         tested_by!(goto_def_for_record_fields);
         tested_by!(goto_def_for_field_init_shorthand);
         if let Some(field_def) = analyzer.resolve_record_field(&record_field) {
-            return Some(from_struct_field(db, field_def));
+            return Some(from_struct_field(sb.db, field_def));
         }
     }
 
-    let ast = ModuleSource::from_child_node(db, name_ref.with_value(&parent));
+    let ast = ModuleSource::from_child_node(sb.db, name_ref.with_value(&parent));
     // FIXME: find correct container and visibility for each case
-    let container = Module::from_definition(db, name_ref.with_value(ast))?;
+    let container = Module::from_definition(sb.db, name_ref.with_value(ast))?;
     let visibility = None;
 
     if let Some(macro_call) = parent.ancestors().find_map(ast::MacroCall::cast) {
         tested_by!(goto_def_for_macros);
-        if let Some(macro_def) = analyzer.resolve_macro_call(db, name_ref.with_value(&macro_call)) {
+        if let Some(macro_def) =
+            analyzer.resolve_macro_call(sb.db, name_ref.with_value(&macro_call))
+        {
             let kind = NameKind::Macro(macro_def);
             return Some(NameDefinition { kind, container, visibility });
         }
     }
 
     let path = name_ref.value.syntax().ancestors().find_map(ast::Path::cast)?;
-    let resolved = analyzer.resolve_path(db, &path)?;
+    let resolved = analyzer.resolve_path(sb.db, &path)?;
     match resolved {
-        PathResolution::Def(def) => Some(from_module_def(db, def, Some(container))),
-        PathResolution::AssocItem(item) => Some(from_assoc_item(db, item)),
+        PathResolution::Def(def) => Some(from_module_def(sb.db, def, Some(container))),
+        PathResolution::AssocItem(item) => Some(from_assoc_item(sb.db, item)),
         PathResolution::Local(local) => {
-            let container = local.module(db);
+            let container = local.module(sb.db);
             let kind = NameKind::Local(local);
             Some(NameDefinition { kind, container, visibility: None })
         }
@@ -188,7 +192,7 @@ pub(crate) fn classify_name_ref(
         }
         PathResolution::SelfType(impl_block) => {
             let kind = NameKind::SelfType(impl_block);
-            let container = impl_block.module(db);
+            let container = impl_block.module(sb.db);
             Some(NameDefinition { kind, container, visibility })
         }
     }
diff --git a/crates/ra_ide/src/syntax_highlighting.rs b/crates/ra_ide/src/syntax_highlighting.rs
index 56a36f587..0411977b9 100644
--- a/crates/ra_ide/src/syntax_highlighting.rs
+++ b/crates/ra_ide/src/syntax_highlighting.rs
@@ -2,7 +2,7 @@
 
 use rustc_hash::{FxHashMap, FxHashSet};
 
-use hir::{InFile, Name};
+use hir::{InFile, Name, SourceBinder};
 use ra_db::SourceDatabase;
 use ra_prof::profile;
 use ra_syntax::{ast, AstNode, Direction, SyntaxElement, SyntaxKind, SyntaxKind::*, TextRange, T};
@@ -84,6 +84,8 @@ pub(crate) fn highlight(db: &RootDatabase, file_id: FileId) -> Vec<HighlightedRa
         hash((file_id, name, shadow_count))
     }
 
+    let mut sb = SourceBinder::new(db);
+
     // Visited nodes to handle highlighting priorities
     // FIXME: retain only ranges here
     let mut highlighted: FxHashSet<SyntaxElement> = FxHashSet::default();
@@ -108,8 +110,8 @@ pub(crate) fn highlight(db: &RootDatabase, file_id: FileId) -> Vec<HighlightedRa
             NAME_REF if node.ancestors().any(|it| it.kind() == ATTR) => continue,
             NAME_REF => {
                 let name_ref = node.as_node().cloned().and_then(ast::NameRef::cast).unwrap();
-                let name_kind =
-                    classify_name_ref(db, InFile::new(file_id.into(), &name_ref)).map(|d| d.kind);
+                let name_kind = classify_name_ref(&mut sb, InFile::new(file_id.into(), &name_ref))
+                    .map(|d| d.kind);
                 match name_kind {
                     Some(name_kind) => {
                         if let Local(local) = &name_kind {
@@ -129,7 +131,7 @@ pub(crate) fn highlight(db: &RootDatabase, file_id: FileId) -> Vec<HighlightedRa
             NAME => {
                 let name = node.as_node().cloned().and_then(ast::Name::cast).unwrap();
                 let name_kind =
-                    classify_name(db, InFile::new(file_id.into(), &name)).map(|d| d.kind);
+                    classify_name(&mut sb, InFile::new(file_id.into(), &name)).map(|d| d.kind);
 
                 if let Some(Local(local)) = &name_kind {
                     if let Some(name) = local.name(db) {
@@ -308,9 +310,12 @@ pre                 { color: #DCDCCC; background: #3F3F3F; font-size: 22px; padd
 
 #[cfg(test)]
 mod tests {
-    use crate::mock_analysis::single_file;
+    use std::fs;
+
     use test_utils::{assert_eq_text, project_dir, read_text};
 
+    use crate::mock_analysis::{single_file, MockAnalysis};
+
     #[test]
     fn test_highlighting() {
         let (analysis, file_id) = single_file(
@@ -357,7 +362,7 @@ impl<X> E<X> {
         let dst_file = project_dir().join("crates/ra_ide/src/snapshots/highlighting.html");
         let actual_html = &analysis.highlight_as_html(file_id, false).unwrap();
         let expected_html = &read_text(&dst_file);
-        std::fs::write(dst_file, &actual_html).unwrap();
+        fs::write(dst_file, &actual_html).unwrap();
         assert_eq_text!(expected_html, actual_html);
     }
 
@@ -383,7 +388,21 @@ fn bar() {
         let dst_file = project_dir().join("crates/ra_ide/src/snapshots/rainbow_highlighting.html");
         let actual_html = &analysis.highlight_as_html(file_id, true).unwrap();
         let expected_html = &read_text(&dst_file);
-        std::fs::write(dst_file, &actual_html).unwrap();
+        fs::write(dst_file, &actual_html).unwrap();
         assert_eq_text!(expected_html, actual_html);
     }
+
+    #[test]
+    fn accidentally_quadratic() {
+        let file = project_dir().join("crates/ra_syntax/test_data/accidentally_quadratic");
+        let src = fs::read_to_string(file).unwrap();
+
+        let mut mock = MockAnalysis::new();
+        let file_id = mock.add_file("/main.rs", &src);
+        let host = mock.analysis_host();
+
+        // let t = std::time::Instant::now();
+        let _ = host.analysis().highlight(file_id).unwrap();
+        // eprintln!("elapsed: {:?}", t.elapsed());
+    }
 }