Repository: rust-analyzer/rust-analyzer
Pull request #7213 (2021-01-08 23:20:38)

Simplify
bors r+


Patch:
diff --git a/Cargo.lock b/Cargo.lock
index bc38c5a37f..57383491a7 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -262,9 +262,9 @@ dependencies = [
 
 [[package]]
 name = "const_fn"
-version = "0.4.5"
+version = "0.4.4"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "28b9d6de7f49e22cf97ad17fc4036ece69300032f45f78f30b4a4482cdc3f4a6"
+checksum = "cd51eab21ab4fd6a3bf889e2d0958c0a6e3a61ad04260325e919e652a2a62826"
 
 [[package]]
 name = "crc32fast"
@@ -774,9 +774,9 @@ checksum = "830d08ce1d1d941e6b30645f1a0eb5643013d835ce3779a5fc208261dbe10f55"
 
 [[package]]
 name = "libc"
-version = "0.2.82"
+version = "0.2.81"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "89203f3fba0a3795506acaad8ebce3c80c0af93f994d5a1d7a0b1eeb23271929"
+checksum = "1482821306169ec4d07f6aca392a4681f66c75c9918aa49641a2595db64053cb"
 
 [[package]]
 name = "libloading"
@@ -1134,9 +1134,9 @@ checksum = "28b9b4df73455c861d7cbf8be42f01d3b373ed7f02e378d55fa84eafc6f638b1"
 
 [[package]]
 name = "pin-project-lite"
-version = "0.2.1"
+version = "0.2.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "e36743d754ccdf9954c2e352ce2d4b106e024c814f6499c2dadff80da9a442d8"
+checksum = "6b063f57ec186e6140e2b8b6921e5f1bd89c7356dda5b33acc5401203ca6131c"
 
 [[package]]
 name = "proc-macro2"
@@ -1449,9 +1449,9 @@ dependencies = [
 
 [[package]]
 name = "semver-parser"
-version = "0.10.2"
+version = "0.10.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "00b0bef5b7f9e0df16536d3961cfb6e84331c065b4066afb39768d0e319411f7"
+checksum = "42ef146c2ad5e5f4b037cd6ce2ebb775401729b19a82040c1beac9d36c7d1428"
 dependencies = [
  "pest",
 ]
@@ -1558,9 +1558,9 @@ version = "0.0.0"
 
 [[package]]
 name = "syn"
-version = "1.0.58"
+version = "1.0.57"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "cc60a3d73ea6594cd712d830cc1f0390fd71542d8c8cd24e70cc54cdfd5e05d5"
+checksum = "4211ce9909eb971f111059df92c45640aad50a619cf55cd76476be803c4c68e6"
 dependencies = [
  "proc-macro2",
  "quote",
@@ -1643,9 +1643,9 @@ checksum = "db3c46be180f1af9673ebb27bc1235396f61ef6965b3fe0dbb2e624deb604f0e"
 
 [[package]]
 name = "thread_local"
-version = "1.1.0"
+version = "1.0.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "bb9bc092d0d51e76b2b19d9d85534ffc9ec2db959a2523cdae0697e2972cd447"
+checksum = "d40c6d1b69745a6ec6fb1ca717914848da4b44ae29d9b3080cbee91d72a69b14"
 dependencies = [
  "lazy_static",
 ]
diff --git a/crates/ide/src/call_hierarchy.rs b/crates/ide/src/call_hierarchy.rs
index 4d8983cb21..b29d1fef9b 100644
--- a/crates/ide/src/call_hierarchy.rs
+++ b/crates/ide/src/call_hierarchy.rs
@@ -5,7 +5,7 @@ use indexmap::IndexMap;
 use hir::Semantics;
 use ide_db::call_info::FnCallNode;
 use ide_db::RootDatabase;
-use syntax::{ast, match_ast, AstNode, TextRange};
+use syntax::{ast, AstNode, TextRange};
 
 use crate::{
     display::TryToNav, goto_definition, references, FilePosition, NavigationTarget, RangeInfo,
@@ -57,15 +57,9 @@ pub(crate) fn incoming_calls(db: &RootDatabase, position: FilePosition) -> Optio
 
         // This target is the containing function
         if let Some(nav) = syntax.ancestors().find_map(|node| {
-            match_ast! {
-                match node {
-                    ast::Fn(it) => {
-                        let def = sema.to_def(&it)?;
-                        def.try_to_nav(sema.db)
-                    },
-                    _ => None,
-                }
-            }
+            let fn_ = ast::Fn::cast(node)?;
+            let def = sema.to_def(&fn_)?;
+            def.try_to_nav(sema.db)
         }) {
             let relative_range = reference.file_range.range;
             calls.add(&nav, relative_range);
@@ -91,17 +85,12 @@ pub(crate) fn outgoing_calls(db: &RootDatabase, position: FilePosition) -> Optio
         .filter_map(|node| FnCallNode::with_node_exact(&node))
         .filter_map(|call_node| {
             let name_ref = call_node.name_ref()?;
-
-            if let Some(func_target) = match &call_node {
+            let func_target = match call_node {
                 FnCallNode::CallExpr(expr) => {
                     //FIXME: Type::as_callable is broken
                     let callable = sema.type_of_expr(&expr.expr()?)?.as_callable(db)?;
                     match callable.kind() {
-                        hir::CallableKind::Function(it) => {
-                            let fn_def: hir::Function = it.into();
-                            let nav = fn_def.try_to_nav(db)?;
-                            Some(nav)
-                        }
+                        hir::CallableKind::Function(it) => it.try_to_nav(db),
                         _ => None,
                     }
                 }
@@ -109,11 +98,8 @@ pub(crate) fn outgoing_calls(db: &RootDatabase, position: FilePosition) -> Optio
                     let function = sema.resolve_method_call(&expr)?;
                     function.try_to_nav(db)
                 }
-            } {
-                Some((func_target, name_ref.syntax().text_range()))
-            } else {
-                None
-            }
+            }?;
+            Some((func_target, name_ref.syntax().text_range()))
         })
         .for_each(|(nav, range)| calls.add(&nav, range));
 
diff --git a/crates/ide/src/syntax_highlighting.rs b/crates/ide/src/syntax_highlighting.rs
index 2eb63a0b7d..ba00852445 100644
--- a/crates/ide/src/syntax_highlighting.rs
+++ b/crates/ide/src/syntax_highlighting.rs
@@ -1,6 +1,3 @@
-mod highlights;
-mod injector;
-
 mod format;
 mod html;
 mod injection;
@@ -72,7 +69,9 @@ pub(crate) fn highlight(
     };
 
     let mut bindings_shadow_count: FxHashMap<Name, u32> = FxHashMap::default();
-    let mut stack = highlights::Highlights::new(range_to_highlight);
+    // We use a stack for the DFS traversal below.
+    // When we leave a node, the we use it to flatten the highlighted ranges.
+    let mut stack = HighlightedRangeStack::new();
 
     let mut current_macro_call: Option<ast::MacroCall> = None;
     let mut current_macro_rules: Option<ast::MacroRules> = None;
@@ -83,8 +82,14 @@ pub(crate) fn highlight(
     // Walk all nodes, keeping track of whether we are inside a macro or not.
     // If in macro, expand it first and highlight the expanded code.
     for event in root.preorder_with_tokens() {
+        match &event {
+            WalkEvent::Enter(_) => stack.push(),
+            WalkEvent::Leave(_) => stack.pop(),
+        };
+
         let event_range = match &event {
-            WalkEvent::Enter(it) | WalkEvent::Leave(it) => it.text_range(),
+            WalkEvent::Enter(it) => it.text_range(),
+            WalkEvent::Leave(it) => it.text_range(),
         };
 
         // Element outside of the viewport, no need to highlight
@@ -133,8 +138,15 @@ pub(crate) fn highlight(
                 if ast::Attr::can_cast(node.kind()) {
                     inside_attribute = false
                 }
-                if let Some((new_comments, inj)) = injection::extract_doc_comments(node) {
-                    injection::highlight_doc_comment(new_comments, inj, &mut stack);
+                if let Some((doctest, range_mapping, new_comments)) =
+                    injection::extract_doc_comments(node)
+                {
+                    injection::highlight_doc_comment(
+                        doctest,
+                        range_mapping,
+                        new_comments,
+                        &mut stack,
+                    );
                 }
             }
             WalkEvent::Enter(NodeOrToken::Node(node)) if ast::Attr::can_cast(node.kind()) => {
@@ -205,6 +217,7 @@ pub(crate) fn highlight(
                 format_string_highlighter.highlight_format_string(&mut stack, &string, range);
                 // Highlight escape sequences
                 if let Some(char_ranges) = string.char_ranges() {
+                    stack.push();
                     for (piece_range, _) in char_ranges.iter().filter(|(_, char)| char.is_ok()) {
                         if string.text()[piece_range.start().into()..].starts_with('\\') {
                             stack.add(HighlightedRange {
@@ -214,12 +227,177 @@ pub(crate) fn highlight(
                             });
                         }
                     }
+                    stack.pop_and_inject(None);
+                }
+            }
+        }
+    }
+
+    stack.flattened()
+}
+
+#[derive(Debug)]
+struct HighlightedRangeStack {
+    stack: Vec<Vec<HighlightedRange>>,
+}
+
+/// We use a stack to implement the flattening logic for the highlighted
+/// syntax ranges.
+impl HighlightedRangeStack {
+    fn new() -> Self {
+        Self { stack: vec![Vec::new()] }
+    }
+
+    fn push(&mut self) {
+        self.stack.push(Vec::new());
+    }
+
+    /// Flattens the highlighted ranges.
+    ///
+    /// For example `#[cfg(feature = "foo")]` contains the nested ranges:
+    /// 1) parent-range: Attribute [0, 23)
+    /// 2) child-range: String [16, 21)
+    ///
+    /// The following code implements the flattening, for our example this results to:
+    /// `[Attribute [0, 16), String [16, 21), Attribute [21, 23)]`
+    fn pop(&mut self) {
+        let children = self.stack.pop().unwrap();
+        let prev = self.stack.last_mut().unwrap();
+        let needs_flattening = !children.is_empty()
+            && !prev.is_empty()
+            && prev.last().unwrap().range.contains_range(children.first().unwrap().range);
+        if !needs_flattening {
+            prev.extend(children);
+        } else {
+            let mut parent = prev.pop().unwrap();
+            for ele in children {
+                assert!(parent.range.contains_range(ele.range));
+
+                let cloned = Self::intersect(&mut parent, &ele);
+                if !parent.range.is_empty() {
+                    prev.push(parent);
+                }
+                prev.push(ele);
+                parent = cloned;
+            }
+            if !parent.range.is_empty() {
+                prev.push(parent);
+            }
+        }
+    }
+
+    /// Intersects the `HighlightedRange` `parent` with `child`.
+    /// `parent` is mutated in place, becoming the range before `child`.
+    /// Returns the range (of the same type as `parent`) *after* `child`.
+    fn intersect(parent: &mut HighlightedRange, child: &HighlightedRange) -> HighlightedRange {
+        assert!(parent.range.contains_range(child.range));
+
+        let mut cloned = parent.clone();
+        parent.range = TextRange::new(parent.range.start(), child.range.start());
+        cloned.range = TextRange::new(child.range.end(), cloned.range.end());
+
+        cloned
+    }
+
+    /// Remove the `HighlightRange` of `parent` that's currently covered by `child`.
+    fn intersect_partial(parent: &mut HighlightedRange, child: &HighlightedRange) {
+        assert!(
+            parent.range.start() <= child.range.start()
+                && parent.range.end() >= child.range.start()
+                && child.range.end() > parent.range.end()
+        );
+
+        parent.range = TextRange::new(parent.range.start(), child.range.start());
+    }
+
+    /// Similar to `pop`, but can modify arbitrary prior ranges (where `pop`)
+    /// can only modify the last range currently on the stack.
+    /// Can be used to do injections that span multiple ranges, like the
+    /// doctest injection below.
+    /// If `overwrite_parent` is non-optional, the highlighting of the parent range
+    /// is overwritten with the argument.
+    ///
+    /// Note that `pop` can be simulated by `pop_and_inject(false)` but the
+    /// latter is computationally more expensive.
+    fn pop_and_inject(&mut self, overwrite_parent: Option<Highlight>) {
+        let mut children = self.stack.pop().unwrap();
+        let prev = self.stack.last_mut().unwrap();
+        children.sort_by_key(|range| range.range.start());
+        prev.sort_by_key(|range| range.range.start());
+
+        for child in children {
+            if let Some(idx) =
+                prev.iter().position(|parent| parent.range.contains_range(child.range))
+            {
+                if let Some(tag) = overwrite_parent {
+                    prev[idx].highlight = tag;
+                }
+
+                let cloned = Self::intersect(&mut prev[idx], &child);
+                let insert_idx = if prev[idx].range.is_empty() {
+                    prev.remove(idx);
+                    idx
+                } else {
+                    idx + 1
+                };
+                prev.insert(insert_idx, child);
+                if !cloned.range.is_empty() {
+                    prev.insert(insert_idx + 1, cloned);
+                }
+            } else {
+                let maybe_idx =
+                    prev.iter().position(|parent| parent.range.contains(child.range.start()));
+                match (overwrite_parent, maybe_idx) {
+                    (Some(_), Some(idx)) => {
+                        Self::intersect_partial(&mut prev[idx], &child);
+                        let insert_idx = if prev[idx].range.is_empty() {
+                            prev.remove(idx);
+                            idx
+                        } else {
+                            idx + 1
+                        };
+                        prev.insert(insert_idx, child);
+                    }
+                    (_, None) => {
+                        let idx = prev
+                            .binary_search_by_key(&child.range.start(), |range| range.range.start())
+                            .unwrap_or_else(|x| x);
+                        prev.insert(idx, child);
+                    }
+                    _ => {
+                        unreachable!("child range should be completely contained in parent range");
+                    }
                 }
             }
         }
     }
 
-    stack.to_vec()
+    fn add(&mut self, range: HighlightedRange) {
+        self.stack
+            .last_mut()
+            .expect("during DFS traversal, the stack must not be empty")
+            .push(range)
+    }
+
+    fn flattened(mut self) -> Vec<HighlightedRange> {
+        assert_eq!(
+            self.stack.len(),
+            1,
+            "after DFS traversal, the stack should only contain a single element"
+        );
+        let mut res = self.stack.pop().unwrap();
+        res.sort_by_key(|range| range.range.start());
+        // Check that ranges are sorted and disjoint
+        for (left, right) in res.iter().zip(res.iter().skip(1)) {
+            assert!(
+                left.range.end() <= right.range.start(),
+                "left: {:#?}, right: {:#?}",
+                left,
+                right
+            );
+        }
+        res
+    }
 }
 
 fn macro_call_range(macro_call: &ast::MacroCall) -> Option<TextRange> {
diff --git a/crates/ide/src/syntax_highlighting/format.rs b/crates/ide/src/syntax_highlighting/format.rs
index ab66b406c8..26416022b8 100644
--- a/crates/ide/src/syntax_highlighting/format.rs
+++ b/crates/ide/src/syntax_highlighting/format.rs
@@ -4,9 +4,9 @@ use syntax::{
     AstNode, AstToken, SyntaxElement, SyntaxKind, SyntaxNode, TextRange,
 };
 
-use crate::{HighlightTag, HighlightedRange, SymbolKind};
-
-use super::highlights::Highlights;
+use crate::{
+    syntax_highlighting::HighlightedRangeStack, HighlightTag, HighlightedRange, SymbolKind,
+};
 
 #[derive(Default)]
 pub(super) struct FormatStringHighlighter {
@@ -39,20 +39,22 @@ impl FormatStringHighlighter {
     }
     pub(super) fn highlight_format_string(
         &self,
-        stack: &mut Highlights,
+        range_stack: &mut HighlightedRangeStack,
         string: &impl HasFormatSpecifier,
         range: TextRange,
     ) {
         if self.format_string.as_ref() == Some(&SyntaxElement::from(string.syntax().clone())) {
+            range_stack.push();
             string.lex_format_specifier(|piece_range, kind| {
                 if let Some(highlight) = highlight_format_specifier(kind) {
-                    stack.add(HighlightedRange {
+                    range_stack.add(HighlightedRange {
                         range: piece_range + range.start(),
                         highlight: highlight.into(),
                         binding_hash: None,
                     });
                 }
             });
+            range_stack.pop();
         }
     }
 }
diff --git a/crates/ide/src/syntax_highlighting/highlights.rs b/crates/ide/src/syntax_highlighting/highlights.rs
deleted file mode 100644
index 3e733c87c6..0000000000
--- a/crates/ide/src/syntax_highlighting/highlights.rs
+++ /dev/null
@@ -1,109 +0,0 @@
-//! Collects a tree of highlighted ranges and flattens it.
-use std::{cmp::Ordering, iter};
-
-use stdx::equal_range_by;
-use syntax::TextRange;
-
-use crate::{HighlightTag, HighlightedRange};
-
-pub(super) struct Highlights {
-    root: Node,
-}
-
-struct Node {
-    highlighted_range: HighlightedRange,
-    nested: Vec<Node>,
-}
-
-impl Highlights {
-    pub(super) fn new(range: TextRange) -> Highlights {
-        Highlights {
-            root: Node::new(HighlightedRange {
-                range,
-                highlight: HighlightTag::Dummy.into(),
-                binding_hash: None,
-            }),
-        }
-    }
-
-    pub(super) fn add(&mut self, highlighted_range: HighlightedRange) {
-        self.root.add(highlighted_range);
-    }
-
-    pub(super) fn to_vec(self) -> Vec<HighlightedRange> {
-        let mut res = Vec::new();
-        self.root.flatten(&mut res);
-        res
-    }
-}
-
-impl Node {
-    fn new(highlighted_range: HighlightedRange) -> Node {
-        Node { highlighted_range, nested: Vec::new() }
-    }
-
-    fn add(&mut self, highlighted_range: HighlightedRange) {
-        assert!(self.highlighted_range.range.contains_range(highlighted_range.range));
-
-        // Fast path
-        if let Some(last) = self.nested.last_mut() {
-            if last.highlighted_range.range.contains_range(highlighted_range.range) {
-                return last.add(highlighted_range);
-            }
-            if last.highlighted_range.range.end() <= highlighted_range.range.start() {
-                return self.nested.push(Node::new(highlighted_range));
-            }
-        }
-
-        let (start, len) = equal_range_by(&self.nested, |n| {
-            ordering(n.highlighted_range.range, highlighted_range.range)
-        });
-
-        if len == 1
-            && self.nested[start].highlighted_range.range.contains_range(highlighted_range.range)
-        {
-            return self.nested[start].add(highlighted_range);
-        }
-
-        let nested = self
-            .nested
-            .splice(start..start + len, iter::once(Node::new(highlighted_range)))
-            .collect::<Vec<_>>();
-        self.nested[start].nested = nested;
-    }
-
-    fn flatten(&self, acc: &mut Vec<HighlightedRange>) {
-        let mut start = self.highlighted_range.range.start();
-        let mut nested = self.nested.iter();
-        loop {
-            let next = nested.next();
-            let end = next.map_or(self.highlighted_range.range.end(), |it| {
-                it.highlighted_range.range.start()
-            });
-            if start < end {
-                acc.push(HighlightedRange {
-                    range: TextRange::new(start, end),
-                    highlight: self.highlighted_range.highlight,
-                    binding_hash: self.highlighted_range.binding_hash,
-                });
-            }
-            start = match next {
-                Some(child) => {
-                    child.flatten(acc);
-                    child.highlighted_range.range.end()
-                }
-                None => break,
-            }
-        }
-    }
-}
-
-pub(super) fn ordering(r1: TextRange, r2: TextRange) -> Ordering {
-    if r1.end() <= r2.start() {
-        Ordering::Less
-    } else if r2.end() <= r1.start() {
-        Ordering::Greater
-    } else {
-        Ordering::Equal
-    }
-}
diff --git a/crates/ide/src/syntax_highlighting/html.rs b/crates/ide/src/syntax_highlighting/html.rs
index 44f611b25d..99ba3a59d3 100644
--- a/crates/ide/src/syntax_highlighting/html.rs
+++ b/crates/ide/src/syntax_highlighting/html.rs
@@ -3,7 +3,7 @@
 use ide_db::base_db::SourceDatabase;
 use oorandom::Rand32;
 use stdx::format_to;
-use syntax::AstNode;
+use syntax::{AstNode, TextRange, TextSize};
 
 use crate::{syntax_highlighting::highlight, FileId, RootDatabase};
 
@@ -22,15 +22,17 @@ pub(crate) fn highlight_as_html(db: &RootDatabase, file_id: FileId, rainbow: boo
 
     let ranges = highlight(db, file_id, None, false);
     let text = parse.tree().syntax().to_string();
+    let mut prev_pos = TextSize::from(0);
     let mut buf = String::new();
     buf.push_str(&STYLE);
     buf.push_str("<pre><code>");
     for range in &ranges {
-        let curr = &text[range.range];
-        if range.highlight.is_empty() {
-            format_to!(buf, "{}", html_escape(curr));
-            continue;
+        if range.range.start() > prev_pos {
+            let curr = &text[TextRange::new(prev_pos, range.range.start())];
+            let text = html_escape(curr);
+            buf.push_str(&text);
         }
+        let curr = &text[TextRange::new(range.range.start(), range.range.end())];
 
         let class = range.highlight.to_string().replace('.', " ");
         let color = match (rainbow, range.binding_hash) {
@@ -40,7 +42,13 @@ pub(crate) fn highlight_as_html(db: &RootDatabase, file_id: FileId, rainbow: boo
             _ => "".into(),
         };
         format_to!(buf, "<span class=\"{}\"{}>{}</span>", class, color, html_escape(curr));
+
+        prev_pos = range.range.end();
     }
+    // Add the remaining (non-highlighted) text
+    let curr = &text[TextRange::new(prev_pos, TextSize::of(&text))];
+    let text = html_escape(curr);
+    buf.push_str(&text);
     buf.push_str("</code></pre>");
     buf
 }
diff --git a/crates/ide/src/syntax_highlighting/injection.rs b/crates/ide/src/syntax_highlighting/injection.rs
index 98ee03e0d9..d6be9708df 100644
--- a/crates/ide/src/syntax_highlighting/injection.rs
+++ b/crates/ide/src/syntax_highlighting/injection.rs
@@ -1,18 +1,18 @@
 //! Syntax highlighting injections such as highlighting of documentation tests.
 
-use std::convert::TryFrom;
+use std::{collections::BTreeMap, convert::TryFrom};
 
 use hir::Semantics;
 use ide_db::call_info::ActiveParameter;
 use itertools::Itertools;
 use syntax::{ast, AstToken, SyntaxNode, SyntaxToken, TextRange, TextSize};
 
-use crate::{Analysis, HighlightModifier, HighlightTag, HighlightedRange, RootDatabase};
+use crate::{Analysis, Highlight, HighlightModifier, HighlightTag, HighlightedRange, RootDatabase};
 
-use super::{highlights::Highlights, injector::Injector};
+use super::HighlightedRangeStack;
 
 pub(super) fn highlight_injection(
-    acc: &mut Highlights,
+    acc: &mut HighlightedRangeStack,
     sema: &Semantics<RootDatabase>,
     literal: ast::String,
     expanded: SyntaxToken,
@@ -98,6 +98,9 @@ impl MarkerInfo {
     }
 }
 
+/// Mapping from extracted documentation code to original code
+type RangesMap = BTreeMap<TextSize, TextSize>;
+
 const RUSTDOC_FENCE: &'static str = "```";
 const RUSTDOC_FENCE_TOKENS: &[&'static str] = &[
     "",
@@ -116,20 +119,20 @@ const RUSTDOC_FENCE_TOKENS: &[&'static str] = &[
 /// Lastly, a vector of new comment highlight ranges (spanning only the
 /// comment prefix) is returned which is used in the syntax highlighting
 /// injection to replace the previous (line-spanning) comment ranges.
-pub(super) fn extract_doc_comments(node: &SyntaxNode) -> Option<(Vec<HighlightedRange>, Injector)> {
-    let mut inj = Injector::default();
+pub(super) fn extract_doc_comments(
+    node: &SyntaxNode,
+) -> Option<(String, RangesMap, Vec<HighlightedRange>)> {
     // wrap the doctest into function body to get correct syntax highlighting
     let prefix = "fn doctest() {\n";
     let suffix = "}\n";
-
-    let mut line_start = TextSize::of(prefix);
+    // Mapping from extracted documentation code to original code
+    let mut range_mapping: RangesMap = BTreeMap::new();
+    let mut line_start = TextSize::try_from(prefix.len()).unwrap();
     let mut is_codeblock = false;
     let mut is_doctest = false;
     // Replace the original, line-spanning comment ranges by new, only comment-prefix
     // spanning comment ranges.
     let mut new_comments = Vec::new();
-
-    inj.add_unmapped(prefix);
     let doctest = node
         .children_with_tokens()
         .filter_map(|el| el.into_token().and_then(ast::Comment::cast))
@@ -166,6 +169,7 @@ pub(super) fn extract_doc_comments(node: &SyntaxNode) -> Option<(Vec<Highlighted
                 pos
             };
 
+            range_mapping.insert(line_start, range.start() + TextSize::try_from(pos).unwrap());
             new_comments.push(HighlightedRange {
                 range: TextRange::new(
                     range.start(),
@@ -175,43 +179,62 @@ pub(super) fn extract_doc_comments(node: &SyntaxNode) -> Option<(Vec<Highlighted
                 binding_hash: None,
             });
             line_start += range.len() - TextSize::try_from(pos).unwrap();
-            line_start += TextSize::of("\n");
+            line_start += TextSize::try_from('\n'.len_utf8()).unwrap();
 
-            inj.add(
-                &line[pos..],
-                TextRange::new(range.start() + TextSize::try_from(pos).unwrap(), range.end()),
-            );
-            inj.add_unmapped("\n");
             line[pos..].to_owned()
         })
         .join("\n");
-    inj.add_unmapped(suffix);
 
     if doctest.is_empty() {
         return None;
     }
 
-    Some((new_comments, inj))
+    let doctest = format!("{}{}{}", prefix, doctest, suffix);
+    Some((doctest, range_mapping, new_comments))
 }
 
 /// Injection of syntax highlighting of doctests.
 pub(super) fn highlight_doc_comment(
+    text: String,
+    range_mapping: RangesMap,
     new_comments: Vec<HighlightedRange>,
-    inj: Injector,
-    stack: &mut Highlights,
+    stack: &mut HighlightedRangeStack,
 ) {
-    let (analysis, tmp_file_id) = Analysis::from_single_file(inj.text().to_string());
-    for comment in new_comments {
-        stack.add(comment);
-    }
+    let (analysis, tmp_file_id) = Analysis::from_single_file(text);
+
+    stack.push();
+    for mut h in analysis.with_db(|db| super::highlight(db, tmp_file_id, None, true)).unwrap() {
+        // Determine start offset and end offset in case of multi-line ranges
+        let mut start_offset = None;
+        let mut end_offset = None;
+        for (line_start, orig_line_start) in range_mapping.range(..h.range.end()).rev() {
+            // It's possible for orig_line_start - line_start to be negative. Add h.range.start()
+            // here and remove it from the end range after the loop below so that the values are
+            // always non-negative.
+            let offset = h.range.start() + orig_line_start - line_start;
+            if line_start <= &h.range.start() {
+                start_offset.get_or_insert(offset);
+                break;
+            } else {
+                end_offset.get_or_insert(offset);
+            }
+        }
+        if let Some(start_offset) = start_offset {
+            h.range = TextRange::new(
+                start_offset,
+                h.range.end() + end_offset.unwrap_or(start_offset) - h.range.start(),
+            );
 
-    for h in analysis.with_db(|db| super::highlight(db, tmp_file_id, None, true)).unwrap() {
-        for r in inj.map_range_up(h.range) {
-            stack.add(HighlightedRange {
-                range: r,
-                highlight: h.highlight | HighlightModifier::Injected,
-                binding_hash: h.binding_hash,
-            });
+            h.highlight |= HighlightModifier::Injected;
+            stack.add(h);
         }
     }
+
+    // Inject the comment prefix highlight ranges
+    stack.push();
+    for comment in new_comments {
+        stack.add(comment);
+    }
+    stack.pop_and_inject(None);
+    stack.pop_and_inject(Some(Highlight::from(HighlightTag::Dummy) | HighlightModifier::Injected));
 }
diff --git a/crates/ide/src/syntax_highlighting/injector.rs b/crates/ide/src/syntax_highlighting/injector.rs
deleted file mode 100644
index 0513a9fd63..0000000000
--- a/crates/ide/src/syntax_highlighting/injector.rs
+++ /dev/null
@@ -1,83 +0,0 @@
-//! Extracts a subsequence of a text document, remembering the mapping of ranges
-//! between original and extracted texts.
-use std::ops::{self, Sub};
-
-use stdx::equal_range_by;
-use syntax::{TextRange, TextSize};
-
-use super::highlights::ordering;
-
-#[derive(Default)]
-pub(super) struct Injector {
-    buf: String,
-    ranges: Vec<(TextRange, Option<Delta<TextSize>>)>,
-}
-
-impl Injector {
-    pub(super) fn add(&mut self, text: &str, source_range: TextRange) {
-        let len = TextSize::of(text);
-        assert_eq!(len, source_range.len());
-
-        let target_range = TextRange::at(TextSize::of(&self.buf), len);
-        self.ranges
-            .push((target_range, Some(Delta::new(target_range.start(), source_range.start()))));
-        self.buf.push_str(text);
-    }
-    pub(super) fn add_unmapped(&mut self, text: &str) {
-        let len = TextSize::of(text);
-
-        let target_range = TextRange::at(TextSize::of(&self.buf), len);
-        self.ranges.push((target_range, None));
-        self.buf.push_str(text);
-    }
-
-    pub(super) fn text(&self) -> &str {
-        &self.buf
-    }
-    pub(super) fn map_range_up(&self, range: TextRange) -> impl Iterator<Item = TextRange> + '_ {
-        let (start, len) = equal_range_by(&self.ranges, |&(r, _)| ordering(r, range));
-        (start..start + len).filter_map(move |i| {
-            let (target_range, delta) = self.ranges[i];
-            let intersection = target_range.intersect(range).unwrap();
-            Some(intersection + delta?)
-        })
-    }
-}
-
-#[derive(Clone, Copy)]
-enum Delta<T> {
-    Add(T),
-    Sub(T),
-}
-
-impl<T> Delta<T> {
-    fn new(from: T, to: T) -> Delta<T>
-    where
-        T: Ord + Sub<Output = T>,
-    {
-        if to >= from {
-            Delta::Add(to - from)
-        } else {
-            Delta::Sub(from - to)
-        }
-    }
-}
-
-impl ops::Add<Delta<TextSize>> for TextSize {
-    type Output = TextSize;
-
-    fn add(self, rhs: Delta<TextSize>) -> TextSize {
-        match rhs {
-            Delta::Add(it) => self + it,
-            Delta::Sub(it) => self - it,
-        }
-    }
-}
-
-impl ops::Add<Delta<TextSize>> for TextRange {
-    type Output = TextRange;
-
-    fn add(self, rhs: Delta<TextSize>) -> TextRange {
-        TextRange::at(self.start() + rhs, self.len())
-    }
-}
diff --git a/crates/ide/src/syntax_highlighting/tags.rs b/crates/ide/src/syntax_highlighting/tags.rs
index a0286b72d9..8b88670798 100644
--- a/crates/ide/src/syntax_highlighting/tags.rs
+++ b/crates/ide/src/syntax_highlighting/tags.rs
@@ -94,13 +94,13 @@ impl HighlightTag {
             HighlightTag::Comment => "comment",
             HighlightTag::EscapeSequence => "escape_sequence",
             HighlightTag::FormatSpecifier => "format_specifier",
+            HighlightTag::Dummy => "dummy",
             HighlightTag::Keyword => "keyword",
             HighlightTag::Punctuation => "punctuation",
             HighlightTag::NumericLiteral => "numeric_literal",
             HighlightTag::Operator => "operator",
             HighlightTag::StringLiteral => "string_literal",
             HighlightTag::UnresolvedReference => "unresolved_reference",
-            HighlightTag::Dummy => "dummy",
         }
     }
 }
@@ -173,9 +173,6 @@ impl Highlight {
     pub(crate) fn new(tag: HighlightTag) -> Highlight {
         Highlight { tag, modifiers: HighlightModifiers::default() }
     }
-    pub fn is_empty(&self) -> bool {
-        self.tag == HighlightTag::Dummy && self.modifiers == HighlightModifiers::default()
-    }
 }
 
 impl ops::BitOr<HighlightModifier> for HighlightTag {
diff --git a/crates/rust-analyzer/src/to_proto.rs b/crates/rust-analyzer/src/to_proto.rs
index 204cae2654..bc9999ddc5 100644
--- a/crates/rust-analyzer/src/to_proto.rs
+++ b/crates/rust-analyzer/src/to_proto.rs
@@ -343,9 +343,6 @@ pub(crate) fn semantic_tokens(
     let mut builder = semantic_tokens::SemanticTokensBuilder::new(id);
 
     for highlight_range in highlights {
-        if highlight_range.highlight.is_empty() {
-            continue;
-        }
         let (type_, mods) = semantic_token_type_and_modifiers(highlight_range.highlight);
         let token_index = semantic_tokens::type_index(type_);
         let modifier_bitset = mods.0;
diff --git a/crates/stdx/src/lib.rs b/crates/stdx/src/lib.rs
index 5aacdb16ed..5332edb09c 100644
--- a/crates/stdx/src/lib.rs
+++ b/crates/stdx/src/lib.rs
@@ -1,5 +1,5 @@
 //! Missing batteries for standard libraries.
-use std::{cmp::Ordering, ops, process, time::Instant};
+use std::{ops, process, time::Instant};
 
 mod macros;
 pub mod panic_context;
@@ -117,12 +117,7 @@ impl<'a> Iterator for LinesWithEnds<'a> {
     }
 }
 
-/// Returns `idx` such that:
-///
-///     ∀ x in slice[..idx]:  pred(x)
-///  && ∀ x in slice[idx..]: !pred(x)
-///
-/// https://github.com/rust-lang/rust/issues/73831
+// https://github.com/rust-lang/rust/issues/73831
 pub fn partition_point<T, P>(slice: &[T], mut pred: P) -> usize
 where
     P: FnMut(&T) -> bool,
@@ -152,15 +147,6 @@ where
     left
 }
 
-pub fn equal_range_by<T, F>(slice: &[T], mut key: F) -> (usize, usize)
-where
-    F: FnMut(&T) -> Ordering,
-{
-    let start = partition_point(slice, |it| key(it) == Ordering::Less);
-    let len = partition_point(&slice[start..], |it| key(it) == Ordering::Equal);
-    (start, len)
-}
-
 pub struct JodChild(pub process::Child);
 
 impl ops::Deref for JodChild {


Test patch:
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 9d42b11c1e..4dd7413ba0 100644
--- a/crates/ide/src/syntax_highlighting/test_data/highlight_doctest.html
+++ b/crates/ide/src/syntax_highlighting/test_data/highlight_doctest.html
@@ -37,18 +37,13 @@ pre                 { color: #DCDCCC; background: #3F3F3F; font-size: 22px; padd
 .unresolved_reference { color: #FC5555; text-decoration: wavy underline; }
 </style>
 <pre><code><span class="comment documentation">/// ```</span>
-<span class="comment documentation">/// </span><span class="keyword injected">let</span><span class="dummy injected"> </span><span class="punctuation injected">_</span><span class="dummy injected"> </span><span class="operator injected">=</span><span class="dummy injected"> </span><span class="string_literal injected">"early doctests should not go boom"</span><span class="punctuation injected">;</span>
-<span class="comment documentation">/// ```</span>
+<span class="comment documentation">/// </span><span class="keyword injected">let</span><span class="dummy injected"> </span><span class="punctuation injected">_</span><span class="dummy injected"> </span><span class="operator injected">=</span><span class="dummy injected"> </span><span class="string_literal injected">"early doctests should not go boom"</span><span class="punctuation injected">;</span><span class="punctuation injected">
+</span><span class="comment documentation">/// ```</span>
 <span class="keyword">struct</span> <span class="struct declaration">Foo</span> <span class="punctuation">{</span>
     <span class="field declaration">bar</span><span class="punctuation">:</span> <span class="builtin_type">bool</span><span class="punctuation">,</span>
 <span class="punctuation">}</span>
 
 <span class="keyword">impl</span> <span class="struct">Foo</span> <span class="punctuation">{</span>
-    <span class="comment documentation">/// ```</span>
-    <span class="comment documentation">/// </span><span class="keyword injected">let</span><span class="dummy injected"> </span><span class="punctuation injected">_</span><span class="dummy injected"> </span><span class="operator injected">=</span><span class="dummy injected"> </span><span class="string_literal injected">"Call me</span>
-    <span class="comment">//    KILLER WHALE</span>
-    <span class="comment documentation">/// </span><span class="string_literal injected">    Ishmael."</span><span class="punctuation injected">;</span>
-    <span class="comment documentation">/// ```</span>
     <span class="keyword">pub</span> <span class="keyword">const</span> <span class="constant declaration associated">bar</span><span class="punctuation">:</span> <span class="builtin_type">bool</span> <span class="operator">=</span> <span class="bool_literal">true</span><span class="punctuation">;</span>
 
     <span class="comment documentation">/// Constructs a new `Foo`.</span>
@@ -57,8 +52,8 @@ pre                 { color: #DCDCCC; background: #3F3F3F; font-size: 22px; padd
     <span class="comment documentation">///</span>
     <span class="comment documentation">/// ```</span>
     <span class="comment documentation">/// #</span><span class="dummy injected"> </span><span class="attribute attribute injected">#</span><span class="attribute attribute injected">!</span><span class="attribute attribute injected">[</span><span class="function attribute injected">allow</span><span class="punctuation attribute injected">(</span><span class="attribute attribute injected">unused_mut</span><span class="punctuation attribute injected">)</span><span class="attribute attribute injected">]</span>
-    <span class="comment documentation">/// </span><span class="keyword injected">let</span><span class="dummy injected"> </span><span class="keyword injected">mut</span><span class="dummy injected"> </span><span class="variable declaration injected mutable">foo</span><span class="punctuation injected">:</span><span class="dummy injected"> </span><span class="struct injected">Foo</span><span class="dummy injected"> </span><span class="operator injected">=</span><span class="dummy injected"> </span><span class="struct injected">Foo</span><span class="operator injected">::</span><span class="function injected">new</span><span class="punctuation injected">(</span><span class="punctuation injected">)</span><span class="punctuation injected">;</span>
-    <span class="comment documentation">/// ```</span>
+    <span class="comment documentation">/// </span><span class="keyword injected">let</span><span class="dummy injected"> </span><span class="keyword injected">mut</span><span class="dummy injected"> </span><span class="variable declaration injected mutable">foo</span><span class="punctuation injected">:</span><span class="dummy injected"> </span><span class="struct injected">Foo</span><span class="dummy injected"> </span><span class="operator injected">=</span><span class="dummy injected"> </span><span class="struct injected">Foo</span><span class="operator injected">::</span><span class="function injected">new</span><span class="punctuation injected">(</span><span class="punctuation injected">)</span><span class="punctuation injected">;</span><span class="punctuation injected">
+</span>    <span class="comment documentation">/// ```</span>
     <span class="keyword">pub</span> <span class="keyword">const</span> <span class="keyword">fn</span> <span class="function declaration static associated">new</span><span class="punctuation">(</span><span class="punctuation">)</span> <span class="operator">-&gt;</span> <span class="struct">Foo</span> <span class="punctuation">{</span>
         <span class="struct">Foo</span> <span class="punctuation">{</span> <span class="field">bar</span><span class="punctuation">:</span> <span class="bool_literal">true</span> <span class="punctuation">}</span>
     <span class="punctuation">}</span>
@@ -77,18 +72,18 @@ pre                 { color: #DCDCCC; background: #3F3F3F; font-size: 22px; padd
     <span class="comment documentation">///</span>
     <span class="comment documentation">/// </span><span class="keyword injected">let</span><span class="dummy injected"> </span><span class="variable declaration injected">bar</span><span class="dummy injected"> </span><span class="operator injected">=</span><span class="dummy injected"> </span><span class="variable injected">foo</span><span class="operator injected">.</span><span class="field injected">bar</span><span class="dummy injected"> </span><span class="operator injected">||</span><span class="dummy injected"> </span><span class="struct injected">Foo</span><span class="operator injected">::</span><span class="constant injected">bar</span><span class="punctuation 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>
+    <span class="comment documentation">/// </span><span class="comment injected">/* multi-line
+    </span><span class="comment documentation">/// </span><span class="comment injected">       comment */</span>
     <span class="comment documentation">///</span>
-    <span class="comment documentation">/// </span><span class="keyword injected">let</span><span class="dummy injected"> </span><span class="variable declaration injected">multi_line_string</span><span class="dummy injected"> </span><span class="operator injected">=</span><span class="dummy injected"> </span><span class="string_literal injected">"Foo</span>
-    <span class="comment documentation">/// </span><span class="string_literal injected">  bar</span>
-    <span class="comment documentation">/// </span><span class="string_literal injected">         "</span><span class="punctuation injected">;</span>
+    <span class="comment documentation">/// </span><span class="keyword injected">let</span><span class="dummy injected"> </span><span class="variable declaration injected">multi_line_string</span><span class="dummy injected"> </span><span class="operator injected">=</span><span class="dummy injected"> </span><span class="string_literal injected">"Foo
+    </span><span class="comment documentation">/// </span><span class="string_literal injected">  bar
+    </span><span class="comment documentation">/// </span><span class="string_literal injected">         "</span><span class="punctuation injected">;</span>
     <span class="comment documentation">///</span>
     <span class="comment documentation">/// ```</span>
     <span class="comment documentation">///</span>
     <span class="comment documentation">/// ```rust,no_run</span>
-    <span class="comment documentation">/// </span><span class="keyword injected">let</span><span class="dummy injected"> </span><span class="variable declaration injected">foobar</span><span class="dummy injected"> </span><span class="operator injected">=</span><span class="dummy injected"> </span><span class="struct injected">Foo</span><span class="operator injected">::</span><span class="function injected">new</span><span class="punctuation injected">(</span><span class="punctuation injected">)</span><span class="operator injected">.</span><span class="function injected">bar</span><span class="punctuation injected">(</span><span class="punctuation injected">)</span><span class="punctuation injected">;</span>
-    <span class="comment documentation">/// ```</span>
+    <span class="comment documentation">/// </span><span class="keyword injected">let</span><span class="dummy injected"> </span><span class="variable declaration injected">foobar</span><span class="dummy injected"> </span><span class="operator injected">=</span><span class="dummy injected"> </span><span class="struct injected">Foo</span><span class="operator injected">::</span><span class="function injected">new</span><span class="punctuation injected">(</span><span class="punctuation injected">)</span><span class="operator injected">.</span><span class="function injected">bar</span><span class="punctuation injected">(</span><span class="punctuation injected">)</span><span class="punctuation injected">;</span><span class="punctuation injected">
+</span>    <span class="comment documentation">/// ```</span>
     <span class="comment documentation">///</span>
     <span class="comment documentation">/// ```sh</span>
     <span class="comment documentation">/// echo 1</span>
@@ -99,8 +94,8 @@ pre                 { color: #DCDCCC; background: #3F3F3F; font-size: 22px; padd
 <span class="punctuation">}</span>
 
 <span class="comment documentation">/// ```</span>
-<span class="comment documentation">/// </span><span class="macro injected">noop!</span><span class="punctuation injected">(</span><span class="numeric_literal injected">1</span><span class="punctuation injected">)</span><span class="punctuation injected">;</span>
-<span class="comment documentation">/// ```</span>
+<span class="comment documentation">/// </span><span class="macro injected">noop!</span><span class="punctuation injected">(</span><span class="numeric_literal injected">1</span><span class="punctuation injected">)</span><span class="punctuation injected">;</span><span class="punctuation injected">
+</span><span class="comment documentation">/// ```</span>
 <span class="keyword">macro_rules</span><span class="punctuation">!</span> <span class="macro declaration">noop</span> <span class="punctuation">{</span>
     <span class="punctuation">(</span><span class="punctuation">$</span>expr<span class="punctuation">:</span>expr<span class="punctuation">)</span> <span class="operator">=</span><span class="punctuation">&gt;</span> <span class="punctuation">{</span>
         <span class="punctuation">$</span>expr
diff --git a/crates/ide/src/syntax_highlighting/tests.rs b/crates/ide/src/syntax_highlighting/tests.rs
index a62704c39e..9e1a3974cb 100644
--- a/crates/ide/src/syntax_highlighting/tests.rs
+++ b/crates/ide/src/syntax_highlighting/tests.rs
@@ -446,11 +446,6 @@ struct Foo {
 }
 
 impl Foo {
-    /// ```
-    /// let _ = "Call me
-    //    KILLER WHALE
-    ///     Ishmael.";
-    /// ```
     pub const bar: bool = true;
 
     /// Constructs a new `Foo`.