6 files changed, 163 insertions, 98 deletions

diff --git a/crates/ide/src/syntax_highlighting/highlight.rs b/crates/ide/src/syntax_highlighting/highlight.rs
index 5ccb84714..18552459b 100644
--- a/crates/ide/src/syntax_highlighting/highlight.rs
+++ b/crates/ide/src/syntax_highlighting/highlight.rs
@@ -12,7 +12,10 @@ use syntax::{
     SyntaxNode, SyntaxToken, T,
 };
 
-use crate::{syntax_highlighting::tags::HlPunct, Highlight, HlMod, HlTag};
+use crate::{
+    syntax_highlighting::tags::{HlOperator, HlPunct},
+    Highlight, HlMod, HlTag,
+};
 
 pub(super) fn element(
     sema: &Semantics<RootDatabase>,
@@ -132,7 +135,7 @@ pub(super) fn element(
         INT_NUMBER | FLOAT_NUMBER => HlTag::NumericLiteral.into(),
         BYTE => HlTag::ByteLiteral.into(),
         CHAR => HlTag::CharLiteral.into(),
-        QUESTION => Highlight::new(HlTag::Operator) | HlMod::ControlFlow,
+        QUESTION => Highlight::new(HlTag::Operator(HlOperator::Other)) | HlMod::ControlFlow,
         LIFETIME => {
             let lifetime = element.into_node().and_then(ast::Lifetime::cast).unwrap();
 
@@ -146,8 +149,11 @@ pub(super) fn element(
             }
         }
         p if p.is_punct() => match p {
+            T![&] if element.parent().and_then(ast::BinExpr::cast).is_some() => {
+                HlTag::Operator(HlOperator::Bitwise).into()
+            }
             T![&] => {
-                let h = HlTag::Operator.into();
+                let h = HlTag::Operator(HlOperator::Other).into();
                 let is_unsafe = element
                     .parent()
                     .and_then(ast::RefExpr::cast)
@@ -159,13 +165,18 @@ pub(super) fn element(
                     h
                 }
             }
-            T![::] | T![->] | T![=>] | T![..] | T![=] | T![@] | T![.] => HlTag::Operator.into(),
+            T![::] | T![->] | T![=>] | T![..] | T![=] | T![@] | T![.] => {
+                HlTag::Operator(HlOperator::Other).into()
+            }
             T![!] if element.parent().and_then(ast::MacroCall::cast).is_some() => {
                 HlTag::Symbol(SymbolKind::Macro).into()
             }
             T![!] if element.parent().and_then(ast::NeverType::cast).is_some() => {
                 HlTag::BuiltinType.into()
             }
+            T![!] if element.parent().and_then(ast::PrefixExpr::cast).is_some() => {
+                HlTag::Operator(HlOperator::Logical).into()
+            }
             T![*] if element.parent().and_then(ast::PtrType::cast).is_some() => {
                 HlTag::Keyword.into()
             }
@@ -175,9 +186,9 @@ pub(super) fn element(
                 let expr = prefix_expr.expr()?;
                 let ty = sema.type_of_expr(&expr)?;
                 if ty.is_raw_ptr() {
-                    HlTag::Operator | HlMod::Unsafe
+                    HlTag::Operator(HlOperator::Other) | HlMod::Unsafe
                 } else if let Some(ast::PrefixOp::Deref) = prefix_expr.op_kind() {
-                    HlTag::Operator.into()
+                    HlTag::Operator(HlOperator::Other).into()
                 } else {
                     HlTag::Punctuation(HlPunct::Other).into()
                 }
@@ -188,19 +199,43 @@ pub(super) fn element(
                 let expr = prefix_expr.expr()?;
                 match expr {
                     ast::Expr::Literal(_) => HlTag::NumericLiteral,
-                    _ => HlTag::Operator,
+                    _ => HlTag::Operator(HlOperator::Other),
                 }
                 .into()
             }
             _ if element.parent().and_then(ast::PrefixExpr::cast).is_some() => {
-                HlTag::Operator.into()
+                HlTag::Operator(HlOperator::Other).into()
+            }
+            T![+] | T![-] | T![*] | T![/] | T![+=] | T![-=] | T![*=] | T![/=]
+                if element.parent().and_then(ast::BinExpr::cast).is_some() =>
+            {
+                HlTag::Operator(HlOperator::Arithmetic).into()
+            }
+            T![|] | T![&] | T![!] | T![^] | T![|=] | T![&=] | T![^=]
+                if element.parent().and_then(ast::BinExpr::cast).is_some() =>
+            {
+                HlTag::Operator(HlOperator::Bitwise).into()
+            }
+            T![&&] | T![||] if element.parent().and_then(ast::BinExpr::cast).is_some() => {
+                HlTag::Operator(HlOperator::Logical).into()
+            }
+            T![>] | T![<] | T![==] | T![>=] | T![<=] | T![!=]
+                if element.parent().and_then(ast::BinExpr::cast).is_some() =>
+            {
+                HlTag::Operator(HlOperator::Comparison).into()
+            }
+            _ if element.parent().and_then(ast::BinExpr::cast).is_some() => {
+                HlTag::Operator(HlOperator::Other).into()
             }
-            _ if element.parent().and_then(ast::BinExpr::cast).is_some() => HlTag::Operator.into(),
             _ if element.parent().and_then(ast::RangeExpr::cast).is_some() => {
-                HlTag::Operator.into()
+                HlTag::Operator(HlOperator::Other).into()
+            }
+            _ if element.parent().and_then(ast::RangePat::cast).is_some() => {
+                HlTag::Operator(HlOperator::Other).into()
+            }
+            _ if element.parent().and_then(ast::RestPat::cast).is_some() => {
+                HlTag::Operator(HlOperator::Other).into()
             }
-            _ if element.parent().and_then(ast::RangePat::cast).is_some() => HlTag::Operator.into(),
-            _ if element.parent().and_then(ast::RestPat::cast).is_some() => HlTag::Operator.into(),
             _ if element.parent().and_then(ast::Attr::cast).is_some() => HlTag::Attribute.into(),
             kind => HlTag::Punctuation(match kind {
                 T!['['] | T![']'] => HlPunct::Bracket,
@@ -323,8 +358,18 @@ fn highlight_def(db: &RootDatabase, def: Definition) -> Highlight {
             hir::ModuleDef::Trait(_) => HlTag::Symbol(SymbolKind::Trait),
             hir::ModuleDef::TypeAlias(type_) => {
                 let mut h = Highlight::new(HlTag::Symbol(SymbolKind::TypeAlias));
-                if type_.as_assoc_item(db).is_some() {
-                    h |= HlMod::Associated
+                if let Some(item) = type_.as_assoc_item(db) {
+                    h |= HlMod::Associated;
+                    match item.container(db) {
+                        AssocItemContainer::Impl(i) => {
+                            if i.trait_(db).is_some() {
+                                h |= HlMod::Trait;
+                            }
+                        }
+                        AssocItemContainer::Trait(_t) => {
+                            h |= HlMod::Trait;
+                        }
+                    }
                 }
                 return h;
             }
diff --git a/crates/ide/src/syntax_highlighting/inject.rs b/crates/ide/src/syntax_highlighting/inject.rs
index b62d43256..bc221d599 100644
--- a/crates/ide/src/syntax_highlighting/inject.rs
+++ b/crates/ide/src/syntax_highlighting/inject.rs
@@ -1,17 +1,17 @@
 //! "Recursive" Syntax highlighting for code in doctests and fixtures.
 
-use std::{mem, ops::Range};
+use std::mem;
 
 use either::Either;
-use hir::{HasAttrs, InFile, Semantics};
-use ide_db::{call_info::ActiveParameter, defs::Definition, SymbolKind};
+use hir::{InFile, Semantics};
+use ide_db::{call_info::ActiveParameter, helpers::rust_doc::is_rust_fence, SymbolKind};
 use syntax::{
     ast::{self, AstNode},
-    match_ast, AstToken, NodeOrToken, SyntaxNode, SyntaxToken, TextRange, TextSize,
+    AstToken, NodeOrToken, SyntaxNode, SyntaxToken, TextRange, TextSize,
 };
 
 use crate::{
-    doc_links::{extract_definitions_from_markdown, resolve_doc_path_for_def},
+    doc_links::{doc_attributes, extract_definitions_from_markdown, resolve_doc_path_for_def},
     Analysis, HlMod, HlRange, HlTag, RootDatabase,
 };
 
@@ -78,44 +78,6 @@ pub(super) fn ra_fixture(
 }
 
 const RUSTDOC_FENCE: &'static str = "```";
-const RUSTDOC_FENCE_TOKENS: &[&'static str] = &[
-    "",
-    "rust",
-    "should_panic",
-    "ignore",
-    "no_run",
-    "compile_fail",
-    "edition2015",
-    "edition2018",
-    "edition2021",
-];
-
-fn doc_attributes<'node>(
-    sema: &Semantics<RootDatabase>,
-    node: &'node SyntaxNode,
-) -> Option<(hir::AttrsWithOwner, Definition)> {
-    match_ast! {
-        match node {
-            ast::SourceFile(it)  => sema.to_def(&it).map(|def| (def.attrs(sema.db), Definition::ModuleDef(hir::ModuleDef::Module(def)))),
-            ast::Module(it)      => sema.to_def(&it).map(|def| (def.attrs(sema.db), Definition::ModuleDef(hir::ModuleDef::Module(def)))),
-            ast::Fn(it)          => sema.to_def(&it).map(|def| (def.attrs(sema.db), Definition::ModuleDef(hir::ModuleDef::Function(def)))),
-            ast::Struct(it)      => sema.to_def(&it).map(|def| (def.attrs(sema.db), Definition::ModuleDef(hir::ModuleDef::Adt(hir::Adt::Struct(def))))),
-            ast::Union(it)       => sema.to_def(&it).map(|def| (def.attrs(sema.db), Definition::ModuleDef(hir::ModuleDef::Adt(hir::Adt::Union(def))))),
-            ast::Enum(it)        => sema.to_def(&it).map(|def| (def.attrs(sema.db), Definition::ModuleDef(hir::ModuleDef::Adt(hir::Adt::Enum(def))))),
-            ast::Variant(it)     => sema.to_def(&it).map(|def| (def.attrs(sema.db), Definition::ModuleDef(hir::ModuleDef::Variant(def)))),
-            ast::Trait(it)       => sema.to_def(&it).map(|def| (def.attrs(sema.db), Definition::ModuleDef(hir::ModuleDef::Trait(def)))),
-            ast::Static(it)      => sema.to_def(&it).map(|def| (def.attrs(sema.db), Definition::ModuleDef(hir::ModuleDef::Static(def)))),
-            ast::Const(it)       => sema.to_def(&it).map(|def| (def.attrs(sema.db), Definition::ModuleDef(hir::ModuleDef::Const(def)))),
-            ast::TypeAlias(it)   => sema.to_def(&it).map(|def| (def.attrs(sema.db), Definition::ModuleDef(hir::ModuleDef::TypeAlias(def)))),
-            ast::Impl(it)        => sema.to_def(&it).map(|def| (def.attrs(sema.db), Definition::SelfType(def))),
-            ast::RecordField(it) => sema.to_def(&it).map(|def| (def.attrs(sema.db), Definition::Field(def))),
-            ast::TupleField(it)  => sema.to_def(&it).map(|def| (def.attrs(sema.db), Definition::Field(def))),
-            ast::Macro(it)       => sema.to_def(&it).map(|def| (def.attrs(sema.db), Definition::Macro(def))),
-            // ast::Use(it) => sema.to_def(&it).map(|def| (Box::new(it) as _, def.attrs(sema.db))),
-            _ => return None
-        }
-    }
-}
 
 /// Injection of syntax highlighting of doctests.
 pub(super) fn doc_comment(
@@ -139,8 +101,28 @@ pub(super) fn doc_comment(
     // Replace the original, line-spanning comment ranges by new, only comment-prefix
     // spanning comment ranges.
     let mut new_comments = Vec::new();
-    let mut intra_doc_links = Vec::new();
     let mut string;
+
+    if let Some((docs, doc_mapping)) = attributes.docs_with_rangemap(sema.db) {
+        extract_definitions_from_markdown(docs.as_str())
+            .into_iter()
+            .filter_map(|(range, link, ns)| {
+                let def = resolve_doc_path_for_def(sema.db, def, &link, ns)?;
+                let InFile { file_id, value: range } = doc_mapping.map(range)?;
+                (file_id == node.file_id).then(|| (range, def))
+            })
+            .for_each(|(range, def)| {
+                hl.add(HlRange {
+                    range,
+                    highlight: module_def_to_hl_tag(def)
+                        | HlMod::Documentation
+                        | HlMod::Injected
+                        | HlMod::IntraDocLink,
+                    binding_hash: None,
+                })
+            });
+    }
+
     for attr in attributes.by_key("doc").attrs() {
         let InFile { file_id, value: src } = attrs_source_map.source_of(&attr);
         if file_id != node.file_id {
@@ -181,30 +163,11 @@ pub(super) fn doc_comment(
                     is_codeblock = !is_codeblock;
                     // Check whether code is rust by inspecting fence guards
                     let guards = &line[idx + RUSTDOC_FENCE.len()..];
-                    let is_rust =
-                        guards.split(',').all(|sub| RUSTDOC_FENCE_TOKENS.contains(&sub.trim()));
+                    let is_rust = is_rust_fence(guards);
                     is_doctest = is_codeblock && is_rust;
                     continue;
                 }
-                None if !is_doctest => {
-                    intra_doc_links.extend(
-                        extract_definitions_from_markdown(line)
-                            .into_iter()
-                            .filter_map(|(range, link, ns)| {
-                                Some(range).zip(resolve_doc_path_for_def(sema.db, def, &link, ns))
-                            })
-                            .map(|(Range { start, end }, def)| {
-                                (
-                                    def,
-                                    TextRange::at(
-                                        prev_range_start + TextSize::from(start as u32),
-                                        TextSize::from((end - start) as u32),
-                                    ),
-                                )
-                            }),
-                    );
-                    continue;
-                }
+                None if !is_doctest => continue,
                 None => (),
             }
 
@@ -223,17 +186,6 @@ pub(super) fn doc_comment(
         }
     }
 
-    for (def, range) in intra_doc_links {
-        hl.add(HlRange {
-            range,
-            highlight: module_def_to_hl_tag(def)
-                | HlMod::Documentation
-                | HlMod::Injected
-                | HlMod::IntraDocLink,
-            binding_hash: None,
-        });
-    }
-
     if new_comments.is_empty() {
         return; // no need to run an analysis on an empty file
     }
diff --git a/crates/ide/src/syntax_highlighting/tags.rs b/crates/ide/src/syntax_highlighting/tags.rs
index 1cec991aa..e58392d67 100644
--- a/crates/ide/src/syntax_highlighting/tags.rs
+++ b/crates/ide/src/syntax_highlighting/tags.rs
@@ -28,7 +28,7 @@ pub enum HlTag {
     FormatSpecifier,
     Keyword,
     NumericLiteral,
-    Operator,
+    Operator(HlOperator),
     Punctuation(HlPunct),
     StringLiteral,
     UnresolvedReference,
@@ -87,6 +87,20 @@ pub enum HlPunct {
     Other,
 }
 
+#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
+pub enum HlOperator {
+    /// |, &, !, ^, |=, &=, ^=
+    Bitwise,
+    /// +, -, *, /, +=, -=, *=, /=
+    Arithmetic,
+    /// &&, ||, !
+    Logical,
+    /// >, <, ==, >=, <=, !=
+    Comparison,
+    ///
+    Other,
+}
+
 impl HlTag {
     fn as_str(self) -> &'static str {
         match self {
@@ -133,7 +147,13 @@ impl HlTag {
                 HlPunct::Other => "punctuation",
             },
             HlTag::NumericLiteral => "numeric_literal",
-            HlTag::Operator => "operator",
+            HlTag::Operator(op) => match op {
+                HlOperator::Bitwise => "bitwise",
+                HlOperator::Arithmetic => "arithmetic",
+                HlOperator::Logical => "logical",
+                HlOperator::Comparison => "comparison",
+                HlOperator::Other => "operator",
+            },
             HlTag::StringLiteral => "string_literal",
             HlTag::UnresolvedReference => "unresolved_reference",
             HlTag::None => "none",
diff --git a/crates/ide/src/syntax_highlighting/test_data/highlight_doctest.html b/crates/ide/src/syntax_highlighting/test_data/highlight_doctest.html
index 045162eb8..6ee6d85fb 100644
--- a/crates/ide/src/syntax_highlighting/test_data/highlight_doctest.html
+++ b/crates/ide/src/syntax_highlighting/test_data/highlight_doctest.html
@@ -76,7 +76,7 @@ pre                 { color: #DCDCCC; background: #3F3F3F; font-size: 22px; padd
     <span class="comment documentation">/// </span><span class="comment injected">// calls bar on foo</span>
     <span class="comment documentation">/// </span><span class="macro injected">assert!</span><span class="parenthesis injected">(</span><span class="none injected">foo</span><span class="operator injected">.</span><span class="none injected">bar</span><span class="parenthesis injected">(</span><span class="parenthesis injected">)</span><span class="parenthesis injected">)</span><span class="semicolon injected">;</span>
     <span class="comment documentation">///</span>
-    <span class="comment documentation">/// </span><span class="keyword injected">let</span><span class="none injected"> </span><span class="variable declaration injected">bar</span><span class="none injected"> </span><span class="operator injected">=</span><span class="none injected"> </span><span class="variable injected">foo</span><span class="operator injected">.</span><span class="field injected">bar</span><span class="none injected"> </span><span class="operator injected">||</span><span class="none injected"> </span><span class="struct injected">Foo</span><span class="operator injected">::</span><span class="constant injected">bar</span><span class="semicolon injected">;</span>
+    <span class="comment documentation">/// </span><span class="keyword injected">let</span><span class="none injected"> </span><span class="variable declaration injected">bar</span><span class="none injected"> </span><span class="operator injected">=</span><span class="none injected"> </span><span class="variable injected">foo</span><span class="operator injected">.</span><span class="field injected">bar</span><span class="none injected"> </span><span class="logical injected">||</span><span class="none injected"> </span><span class="struct injected">Foo</span><span class="operator injected">::</span><span class="constant injected">bar</span><span class="semicolon injected">;</span>
     <span class="comment documentation">///</span>
     <span class="comment documentation">/// </span><span class="comment injected">/* multi-line</span>
     <span class="comment documentation">/// </span><span class="comment injected">       comment */</span>
@@ -100,10 +100,18 @@ pre                 { color: #DCDCCC; background: #3F3F3F; font-size: 22px; padd
 <span class="brace">}</span>
 
 <span class="comment documentation">/// </span><span class="struct documentation intra_doc_link injected">[`Foo`](Foo)</span><span class="comment documentation"> is a struct</span>
-<span class="comment documentation">/// </span><span class="function documentation intra_doc_link injected">[`all_the_links`](all_the_links)</span><span class="comment documentation"> is this function</span>
+<span class="comment documentation">/// This function is &gt; </span><span class="function documentation intra_doc_link injected">[`all_the_links`](all_the_links)</span><span class="comment documentation"> &lt;</span>
 <span class="comment documentation">/// [`noop`](noop) is a macro below</span>
+<span class="comment documentation">/// </span><span class="struct documentation intra_doc_link injected">[`Item`]</span><span class="comment documentation"> is a struct in the module </span><span class="module documentation intra_doc_link injected">[`module`]</span>
+<span class="comment documentation">///</span>
+<span class="comment documentation">/// [`Item`]: module::Item</span>
+<span class="comment documentation">/// [mix_and_match]: ThisShouldntResolve</span>
 <span class="keyword">pub</span> <span class="keyword">fn</span> <span class="function declaration">all_the_links</span><span class="parenthesis">(</span><span class="parenthesis">)</span> <span class="brace">{</span><span class="brace">}</span>
 
+<span class="keyword">pub</span> <span class="keyword">mod</span> <span class="module declaration">module</span> <span class="brace">{</span>
+    <span class="keyword">pub</span> <span class="keyword">struct</span> <span class="struct declaration">Item</span><span class="semicolon">;</span>
+<span class="brace">}</span>
+
 <span class="comment documentation">/// ```</span>
 <span class="comment documentation">/// </span><span class="macro injected">noop!</span><span class="parenthesis injected">(</span><span class="numeric_literal injected">1</span><span class="parenthesis injected">)</span><span class="semicolon injected">;</span>
 <span class="comment documentation">/// ```</span>
diff --git a/crates/ide/src/syntax_highlighting/test_data/highlighting.html b/crates/ide/src/syntax_highlighting/test_data/highlighting.html
index 973173254..c43bcb691 100644
--- a/crates/ide/src/syntax_highlighting/test_data/highlighting.html
+++ b/crates/ide/src/syntax_highlighting/test_data/highlighting.html
@@ -213,7 +213,7 @@ pre                 { color: #DCDCCC; background: #3F3F3F; font-size: 22px; padd
     <span class="keyword">let</span> <span class="variable declaration">baz</span> <span class="operator">=</span> <span class="numeric_literal">-</span><span class="numeric_literal">42</span><span class="semicolon">;</span>
     <span class="keyword">let</span> <span class="variable declaration">baz</span> <span class="operator">=</span> <span class="operator">-</span><span class="variable">baz</span><span class="semicolon">;</span>
 
-    <span class="keyword">let</span> <span class="punctuation">_</span> <span class="operator">=</span> <span class="operator">!</span><span class="bool_literal">true</span><span class="semicolon">;</span>
+    <span class="keyword">let</span> <span class="punctuation">_</span> <span class="operator">=</span> <span class="logical">!</span><span class="bool_literal">true</span><span class="semicolon">;</span>
 
     <span class="label declaration">'foo</span><span class="colon">:</span> <span class="keyword control">loop</span> <span class="brace">{</span>
         <span class="keyword control">break</span> <span class="label">'foo</span><span class="semicolon">;</span>
diff --git a/crates/ide/src/syntax_highlighting/tests.rs b/crates/ide/src/syntax_highlighting/tests.rs
index 369ae0972..17cc6334b 100644
--- a/crates/ide/src/syntax_highlighting/tests.rs
+++ b/crates/ide/src/syntax_highlighting/tests.rs
@@ -1,6 +1,8 @@
+use std::time::Instant;
+
 use expect_test::{expect_file, ExpectFile};
 use ide_db::SymbolKind;
-use test_utils::{bench, bench_fixture, skip_slow_tests};
+use test_utils::{bench, bench_fixture, skip_slow_tests, AssertLinear};
 
 use crate::{fixture, FileRange, HlTag, TextRange};
 
@@ -258,6 +260,36 @@ fn benchmark_syntax_highlighting_long_struct() {
 }
 
 #[test]
+fn syntax_highlighting_not_quadratic() {
+    if skip_slow_tests() {
+        return;
+    }
+
+    let mut al = AssertLinear::default();
+    while al.next_round() {
+        for i in 6..=10 {
+            let n = 1 << i;
+
+            let fixture = bench_fixture::big_struct_n(n);
+            let (analysis, file_id) = fixture::file(&fixture);
+
+            let time = Instant::now();
+
+            let hash = analysis
+                .highlight(file_id)
+                .unwrap()
+                .iter()
+                .filter(|it| it.highlight.tag == HlTag::Symbol(SymbolKind::Struct))
+                .count();
+            assert!(hash > n as usize);
+
+            let elapsed = time.elapsed();
+            al.sample(n as f64, elapsed.as_millis() as f64);
+        }
+    }
+}
+
+#[test]
 fn benchmark_syntax_highlighting_parser() {
     if skip_slow_tests() {
         return;
@@ -275,7 +307,7 @@ fn benchmark_syntax_highlighting_parser() {
             .filter(|it| it.highlight.tag == HlTag::Symbol(SymbolKind::Function))
             .count()
     };
-    assert_eq!(hash, 1629);
+    assert_eq!(hash, 1632);
 }
 
 #[test]
@@ -544,10 +576,18 @@ impl Foo {
 }
 
 /// [`Foo`](Foo) is a struct
-/// [`all_the_links`](all_the_links) is this function
+/// This function is > [`all_the_links`](all_the_links) <
 /// [`noop`](noop) is a macro below
+/// [`Item`] is a struct in the module [`module`]
+///
+/// [`Item`]: module::Item
+/// [mix_and_match]: ThisShouldntResolve
 pub fn all_the_links() {}
 
+pub mod module {
+    pub struct Item;
+}
+
 /// ```
 /// noop!(1);
 /// ```