From e30c1c3fbf8f70336d985b2b73e5b0f45f3b95f5 Mon Sep 17 00:00:00 2001 From: Aleksey Kladov Date: Fri, 8 Jan 2021 01:39:02 +0300 Subject: Simplify highlighting infra This also fixes the killer whale bug --- crates/ide/src/syntax_highlighting.rs | 194 +-------------------- crates/ide/src/syntax_highlighting/format.rs | 12 +- crates/ide/src/syntax_highlighting/highlights.rs | 109 ++++++++++++ crates/ide/src/syntax_highlighting/html.rs | 18 +- crates/ide/src/syntax_highlighting/injection.rs | 85 ++++----- crates/ide/src/syntax_highlighting/injector.rs | 83 +++++++++ crates/ide/src/syntax_highlighting/tags.rs | 5 +- .../test_data/highlight_doctest.html | 31 ++-- crates/ide/src/syntax_highlighting/tests.rs | 5 + crates/rust-analyzer/src/to_proto.rs | 3 + crates/stdx/src/lib.rs | 18 +- 11 files changed, 287 insertions(+), 276 deletions(-) create mode 100644 crates/ide/src/syntax_highlighting/highlights.rs create mode 100644 crates/ide/src/syntax_highlighting/injector.rs 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 = 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 = None; let mut current_macro_rules: Option = 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>, -} - -/// 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) { - 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 { - 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 { 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, +} + +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 { + 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::>(); + self.nested[start].nested = nested; + } + + fn flatten(&self, acc: &mut Vec) { + 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("
");
     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, "{}", 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("
"); 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, literal: ast::String, expanded: SyntaxToken, @@ -98,9 +98,6 @@ impl MarkerInfo { } } -/// Mapping from extracted documentation code to original code -type RangesMap = BTreeMap; - 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)> { +pub(super) fn extract_doc_comments(node: &SyntaxNode) -> Option<(Vec, 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, - 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>)>, +} + +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 + '_ { + 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 { + Add(T), + Sub(T), +} + +impl Delta { + fn new(from: T, to: T) -> Delta + where + T: Ord + Sub, + { + if to >= from { + Delta::Add(to - from) + } else { + Delta::Sub(from - to) + } + } +} + +impl ops::Add> for TextSize { + type Output = TextSize; + + fn add(self, rhs: Delta) -> TextSize { + match rhs { + Delta::Add(it) => self + it, + Delta::Sub(it) => self - it, + } + } +} + +impl ops::Add> for TextRange { + type Output = TextRange; + + fn add(self, rhs: Delta) -> 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 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; } 
/// ```
-/// let _ = "early doctests should not go boom";
-/// ```
+/// let _ = "early doctests should not go boom";
+/// ```
 struct Foo {
     bar: bool,
 }
 
 impl Foo {
+    /// ```
+    /// let _ = "Call me
+    //    KILLER WHALE
+    ///     Ishmael.";
+    /// ```
     pub const bar: bool = true;
 
     /// Constructs a new `Foo`.
@@ -52,8 +57,8 @@ pre                 { color: #DCDCCC; background: #3F3F3F; font-size: 22px; padd
     ///
     /// ```
     /// # #![allow(unused_mut)]
-    /// let mut foo: Foo = Foo::new();
-    /// ```
+    /// let mut foo: Foo = Foo::new();
+    /// ```
     pub const fn new() -> Foo {
         Foo { bar: true }
     }
@@ -72,18 +77,18 @@ pre                 { color: #DCDCCC; background: #3F3F3F; font-size: 22px; padd
     ///
     /// let bar = foo.bar || Foo::bar;
     ///
-    /// /* multi-line
-    ///        comment */
+    /// /* multi-line
+    ///        comment */
     ///
-    /// let multi_line_string = "Foo
-    ///   bar
-    ///          ";
+    /// let multi_line_string = "Foo
+    ///   bar
+    ///          ";
     ///
     /// ```
     ///
     /// ```rust,no_run
-    /// let foobar = Foo::new().bar();
-    /// ```
+    /// let foobar = Foo::new().bar();
+    /// ```
     ///
     /// ```sh
     /// echo 1
@@ -94,8 +99,8 @@ pre                 { color: #DCDCCC; background: #3F3F3F; font-size: 22px; padd
 }
 
 /// ```
-/// noop!(1);
-/// ```
+/// noop!(1);
+/// ```
 macro_rules! noop {
     ($expr:expr) => {
         $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(slice: &[T], mut pred: P) -> usize
 where
     P: FnMut(&T) -> bool,
@@ -147,6 +152,15 @@ where
     left
 }
 
+pub fn equal_range_by(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 {
-- 
cgit v1.2.3