11 files changed, 287 insertions, 276 deletions

diff --git a/crates/ide/src/syntax_highlighting.rs b/crates/ide/src/syntax_highlighting.rs
index ba0085244..2eb63a0b7 100644
--- a/crates/ide/src/syntax_highlighting.rs
+++ b/crates/ide/src/syntax_highlighting.rs
@@ -1,3 +1,6 @@
+mod highlights;
+mod injector;
+
 mod format;
 mod html;
 mod injection;
@@ -69,9 +72,7 @@ pub(crate) fn highlight(
     };
 
     let mut bindings_shadow_count: FxHashMap<Name, u32> = FxHashMap::default();
-    // 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 stack = highlights::Highlights::new(range_to_highlight);
 
     let mut current_macro_call: Option<ast::MacroCall> = None;
     let mut current_macro_rules: Option<ast::MacroRules> = None;
@@ -82,14 +83,8 @@ 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) => it.text_range(),
-            WalkEvent::Leave(it) => it.text_range(),
+            WalkEvent::Enter(it) | WalkEvent::Leave(it) => it.text_range(),
         };
 
         // Element outside of the viewport, no need to highlight
@@ -138,15 +133,8 @@ pub(crate) fn highlight(
                 if ast::Attr::can_cast(node.kind()) {
                     inside_attribute = false
                 }
-                if let Some((doctest, range_mapping, new_comments)) =
-                    injection::extract_doc_comments(node)
-                {
-                    injection::highlight_doc_comment(
-                        doctest,
-                        range_mapping,
-                        new_comments,
-                        &mut stack,
-                    );
+                if let Some((new_comments, inj)) = injection::extract_doc_comments(node) {
+                    injection::highlight_doc_comment(new_comments, inj, &mut stack);
                 }
             }
             WalkEvent::Enter(NodeOrToken::Node(node)) if ast::Attr::can_cast(node.kind()) => {
@@ -217,7 +205,6 @@ 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 {
@@ -227,177 +214,12 @@ 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");
-                    }
                 }
             }
         }
     }
 
-    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
-    }
+    stack.to_vec()
 }
 
 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 26416022b..ab66b406c 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::{
-    syntax_highlighting::HighlightedRangeStack, HighlightTag, HighlightedRange, SymbolKind,
-};
+use crate::{HighlightTag, HighlightedRange, SymbolKind};
+
+use super::highlights::Highlights;
 
 #[derive(Default)]
 pub(super) struct FormatStringHighlighter {
@@ -39,22 +39,20 @@ impl FormatStringHighlighter {
     }
     pub(super) fn highlight_format_string(
         &self,
-        range_stack: &mut HighlightedRangeStack,
+        stack: &mut Highlights,
         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) {
-                    range_stack.add(HighlightedRange {
+                    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
new file mode 100644
index 000000000..3e733c87c
--- /dev/null
+++ b/crates/ide/src/syntax_highlighting/highlights.rs
@@ -0,0 +1,109 @@
+//! 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 99ba3a59d..44f611b25 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, TextRange, TextSize};
+use syntax::AstNode;
 
 use crate::{syntax_highlighting::highlight, FileId, RootDatabase};
 
@@ -22,17 +22,15 @@ 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 {
-        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[range.range];
+        if range.highlight.is_empty() {
+            format_to!(buf, "{}", html_escape(curr));
+            continue;
         }
-        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) {
@@ -42,13 +40,7 @@ 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 d6be9708d..98ee03e0d 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::{collections::BTreeMap, convert::TryFrom};
+use std::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, Highlight, HighlightModifier, HighlightTag, HighlightedRange, RootDatabase};
+use crate::{Analysis, HighlightModifier, HighlightTag, HighlightedRange, RootDatabase};
 
-use super::HighlightedRangeStack;
+use super::{highlights::Highlights, injector::Injector};
 
 pub(super) fn highlight_injection(
-    acc: &mut HighlightedRangeStack,
+    acc: &mut Highlights,
     sema: &Semantics<RootDatabase>,
     literal: ast::String,
     expanded: SyntaxToken,
@@ -98,9 +98,6 @@ 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] = &[
     "",
@@ -119,20 +116,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<(String, RangesMap, Vec<HighlightedRange>)> {
+pub(super) fn extract_doc_comments(node: &SyntaxNode) -> Option<(Vec<HighlightedRange>, Injector)> {
+    let mut inj = Injector::default();
     // wrap the doctest into function body to get correct syntax highlighting
     let prefix = "fn doctest() {\n";
     let suffix = "}\n";
-    // 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 line_start = TextSize::of(prefix);
     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))
@@ -169,7 +166,6 @@ pub(super) fn extract_doc_comments(
                 pos
             };
 
-            range_mapping.insert(line_start, range.start() + TextSize::try_from(pos).unwrap());
             new_comments.push(HighlightedRange {
                 range: TextRange::new(
                     range.start(),
@@ -179,62 +175,43 @@ pub(super) fn extract_doc_comments(
                 binding_hash: None,
             });
             line_start += range.len() - TextSize::try_from(pos).unwrap();
-            line_start += TextSize::try_from('\n'.len_utf8()).unwrap();
+            line_start += TextSize::of("\n");
 
+            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;
     }
 
-    let doctest = format!("{}{}{}", prefix, doctest, suffix);
-    Some((doctest, range_mapping, new_comments))
+    Some((new_comments, inj))
 }
 
 /// Injection of syntax highlighting of doctests.
 pub(super) fn highlight_doc_comment(
-    text: String,
-    range_mapping: RangesMap,
     new_comments: Vec<HighlightedRange>,
-    stack: &mut HighlightedRangeStack,
+    inj: Injector,
+    stack: &mut Highlights,
 ) {
-    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(),
-            );
-
-            h.highlight |= HighlightModifier::Injected;
-            stack.add(h);
-        }
-    }
-
-    // Inject the comment prefix highlight ranges
-    stack.push();
+    let (analysis, tmp_file_id) = Analysis::from_single_file(inj.text().to_string());
     for comment in new_comments {
         stack.add(comment);
     }
-    stack.pop_and_inject(None);
-    stack.pop_and_inject(Some(Highlight::from(HighlightTag::Dummy) | HighlightModifier::Injected));
+
+    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,
+            });
+        }
+    }
 }
diff --git a/crates/ide/src/syntax_highlighting/injector.rs b/crates/ide/src/syntax_highlighting/injector.rs
new file mode 100644
index 000000000..0513a9fd6
--- /dev/null
+++ b/crates/ide/src/syntax_highlighting/injector.rs
@@ -0,0 +1,83 @@
+//! 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 8b8867079..a0286b72d 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,6 +173,9 @@ 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/ide/src/syntax_highlighting/test_data/highlight_doctest.html b/crates/ide/src/syntax_highlighting/test_data/highlight_doctest.html
index 4dd7413ba..9d42b11c1 100644
--- a/crates/ide/src/syntax_highlighting/test_data/highlight_doctest.html
+++ b/crates/ide/src/syntax_highlighting/test_data/highlight_doctest.html
@@ -37,13 +37,18 @@ 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="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="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>
@@ -52,8 +57,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="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="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>
@@ -72,18 +77,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="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="comment documentation">/// ```</span>
     <span class="comment documentation">///</span>
     <span class="comment documentation">/// ```sh</span>
     <span class="comment documentation">/// echo 1</span>
@@ -94,8 +99,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="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="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 9e1a3974c..a62704c39 100644
--- a/crates/ide/src/syntax_highlighting/tests.rs
+++ b/crates/ide/src/syntax_highlighting/tests.rs
@@ -446,6 +446,11 @@ struct Foo {
 }
 
 impl Foo {
+    /// ```
+    /// let _ = "Call me
+    //    KILLER WHALE
+    ///     Ishmael.";
+    /// ```
     pub const bar: bool = true;
 
     /// Constructs a new `Foo`.
diff --git a/crates/rust-analyzer/src/to_proto.rs b/crates/rust-analyzer/src/to_proto.rs
index bc9999ddc..204cae265 100644
--- a/crates/rust-analyzer/src/to_proto.rs
+++ b/crates/rust-analyzer/src/to_proto.rs
@@ -343,6 +343,9 @@ 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 5332edb09..5aacdb16e 100644
--- a/crates/stdx/src/lib.rs
+++ b/crates/stdx/src/lib.rs
@@ -1,5 +1,5 @@
 //! Missing batteries for standard libraries.
-use std::{ops, process, time::Instant};
+use std::{cmp::Ordering, ops, process, time::Instant};
 
 mod macros;
 pub mod panic_context;
@@ -117,7 +117,12 @@ impl<'a> Iterator for LinesWithEnds<'a> {
     }
 }
 
-// https://github.com/rust-lang/rust/issues/73831
+/// Returns `idx` such that:
+///
+///     ∀ x in slice[..idx]:  pred(x)
+///  && ∀ x in slice[idx..]: !pred(x)
+///
+/// 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,
@@ -147,6 +152,15 @@ 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 {