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/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 + 8 files changed, 260 insertions(+), 88 deletions(-) create mode 100644 crates/ide/src/syntax_highlighting/highlights.rs create mode 100644 crates/ide/src/syntax_highlighting/injector.rs (limited to 'crates/ide/src/syntax_highlighting') 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`.
-- 
cgit v1.2.3