[clangd] Added a colorizer to the vscode extension.

[jvikstrom]

Summary

Adds the main colorizer component. It colorizes every time clangd sends a publishSemanticHighlighting notification.
Every time it colorizes it does a full recolorization (removes all decorations from the editor and applies new ones). The reason for this is that all ranges for the same scope share a TextEditorDecorationType. This is due to TextEditorDecorationTypes being very expensive to create. The prototype used one DecorationType per range but that ran into very big performance problems (it took >100 ms to apply 600 lines of highlightings which froze the editor).

This version does not share the problem of being too slow, but there is probably potential to optimize it even more.

The Colorizer uses a FileColorizer interface to make it possible to mock out all the code that applies colorizations to a specific editor so that we can test it.

No document/texteditor lifecycle management code in this CL, that will come in the next one.

[hokein]

clang-tools-extra/clangd/clients/clangd-vscode/src/semantic-highlighting.ts

144

The generic T doesnt seem to be used?

Regarding the name, the word colorization is from vscode cpp-tools extension, I think in clangd we should keep using Hightlight for consistency, maybe use Highlighter?

145

could you add some documentation for these fields?

146

It seems that, all files are sharing with duplicated implementations in this patch, storing duplications is wasteful.

Maybe we could make the colorize method as a virtual method -- in the unittest, we create a subclass of Colorizer and override the colorize method.

164

we are patching the incremental diff to get a "global" highlighting for the whole file, but it maybe not correct -- clangd doesn't emit diff outside of the max line number of the file, if we delete a few lines at the end of the file, then we will keep the removed lines in the map.

I think this is a current limitation, could you check with the current behavior of vscode if we pass a out-of-range to the decoration API?

[jvikstrom]

Renamed colorizer to highlighter and added FIXME about highlightings below eof.

[hokein]

clang-tools-extra/clangd/clients/clangd-vscode/src/semantic-highlighting.ts

135

I'm not convinced that we need this interface.

With the current implementation (create new TextEditorDecorationTypes every time we do a re-highlighting), we'd need to save the old decorations in order to dispose them when applying new decorations.

but if we create the TextEditorDecorationTypes at Initialization and reuse them in re-highlighting, then we probably don't need to depose them manually, the vscode API seems do that for us, so I think we'd better to do that in this patch as it would simplify the current implementation.

So the APIs would looks like below. In unittest, we just override applyDecorations method.

class Highlighter {

public Initialize(themeRuleMatcher: ThemeRuleMatcher) {
   // build a scopeIndex => TextEditorDecorationTypes table
}

public highlight(fileUri: string, highlightings: SemanticHighlightingLine[]) {
   // update and patch the highlighting cache.
   // invoke getDecorations
   // invoke applyDecorations
}

protect applyDecorations(decorations...) {
   // invoke vscode API to apply the decorations.
}

private getDecorations(hightligtings...) {
}

177

I'd name it Initialize.

183

the name of this public API is confusing, the name indicates it just sets the data, but actually it does more stuff like doing the highlightings.

I think we may get rid of this function, by just exposing the highlight API. see my above comment.

200

could we name it fileUri? and elsewhere

218

nit: I think we can just do const lines: SemanticHighlightingLine[] = Array.from(this.files.get(uriString).values())?

220

nit: pull out this part into a new method e.g. getDecorations

[jvikstrom]

Rewrote the Highlighter class as we can override the highlighting method for the tests.

[jvikstrom]

I had completely forgotten we could just override the applyHighlightings method in the tests, everything is much simpler now.

Basically this entire CL was rewritten just now.

[jvikstrom]

Added missing protected and comment.

[hokein]

thanks, looks better now. Some more comments on the test code.

clang-tools-extra/clangd/clients/clangd-vscode/src/extension.ts

3 ↗

(On Diff #216624)

I'd name it semanticHighlighting

clang-tools-extra/clangd/clients/clangd-vscode/src/semantic-highlighting.ts

129

nit: mention the index is the scopeIndex?

136

nit: the comment is stale now. I believe this function is only called whenever we reload a theme or at the first launch of the extension.

138

if this.decorationsTypes is not empty (when this API is called multiple times), I think we need to call the dispose method to release the resource they hold.

140

just want to confirm: if we fail to find a matched theme rule, we return an empty decoration. I think vscode just doesn't do anything on an empty color?

158

nit: tokens => HighlightingLines.

191

nit: add a comment, we don't apply highlights when the class is not ready/initialized.

clang-tools-extra/clangd/clients/clangd-vscode/test/semantic-highlighting.test.ts

80

could you add a comment you override this so that it can be access from the test?

93

nit: please use a more descriptive name, e.g. HightlightsInLine.

94

I believe the test code is correct, but the code here/below is complex and hard to follow. I think we need make the code more readable/understandable.

some suggestions:

• the line number is implicitly indicated by the index of the array, I think we can add one more field line to the structure (call HighlightingTokens).
• and creates some helper functions (with proper names) that take the HighlightingTokens as parameter and generate the data you need e.g. SemanticHighlightingLine[], vscode.Range.

[jvikstrom]

Made tests more readable.

clang-tools-extra/clangd/clients/clangd-vscode/src/semantic-highlighting.ts

136

It's should only called when a theme is loaded (and we happen to load a theme when we initialize, but it's async).
Don't see why the comment is stale though, it seems to describe what it does to me.

140

vscode indeed does not do anything on empty colors.

clang-tools-extra/clangd/clients/clangd-vscode/test/semantic-highlighting.test.ts

94

Started exporting the SemanticHighlightingLine interface and use that format in the tests to not create more interfaces (also means we don't need a helper for creating the SemanticHighlightingLine).

[hokein]

thanks, looks great, looking forward to use it, just a few more nits.

Please update the patch description before committing.

clang-tools-extra/clangd/clients/clangd-vscode/src/semantic-highlighting.ts

58–60

nit: I think we can remove this field since it is not used in this class.

136

IIRC, the comment here was move from setThemeRuleMatcher, but now it's named initialize, I'd expect the comment is more specific about *initialization* of the class -- when this method should be called, and what it does (in a high level).

140

could you add a comment for this?

171

I think we should comment this method as normal methods.

172

nit: spell the return type.

clang-tools-extra/clangd/clients/clangd-vscode/test/semantic-highlighting.test.ts

82

nit: I'd inline the createRange here, since we only use it once.

103

nit: use some readable name, e.g. file1, file2?

106

nit: inline the rules here.

137

the array contains a single element, I'd use semanticHighlighting.SemanticHighlightingLine and name it HighlightingsInLine1

158

maybe just [HighlightingsInLine1, ...highlightingsInLine.slice(1)]?

clang-tools-extra/clangd/clients/clangd-vscode/src/semantic-highlighting.ts

 interface SemanticHighlightingToken {
   // Start column for this token.
   character: number;
   // Length of the token.
   length: number;
   // The TextMate scope index to the clangd scope lookup table.
   scopeIndex: number;
 }
+// A line of decoded highlightings from the data clangd sent.
+interface SemanticHighlightingLine {
+  // The zero-based line position in the text document.
+  line: number;
+  // All SemanticHighlightingTokens on the line.
+  tokens: SemanticHighlightingToken[];
+}
 
 // Language server push notification providing the semantic highlighting
 // information for a text document.
 export const NotificationType =
     new vscodelc.NotificationType<SemanticHighlightingParams, void>(
         'textDocument/semanticHighlighting');
 
 // The feature that should be registered in the vscode lsp for enabling
 // experimental semantic highlighting.
 export class SemanticHighlightingFeature implements vscodelc.StaticFeature {
   // The TextMate scope lookup table. A token with scope index i has the scopes
   // on index i in the lookup table.
   scopeLookupTable: string[][];
   // The rules for the current theme.
   themeRuleMatcher: ThemeRuleMatcher;
+  // The object that colorizes the highlightings clangd sends.
+  colorizer: Colorizer<FileColorizer>;
   fillClientCapabilities(capabilities: vscodelc.ClientCapabilities) {
     // Extend the ClientCapabilities type and add semantic highlighting
     // capability to the object.
     const textDocumentCapabilities: vscodelc.TextDocumentClientCapabilities&
         {semanticHighlightingCapabilities?: {semanticHighlighting : boolean}} =
         capabilities.textDocument;
     textDocumentCapabilities.semanticHighlightingCapabilities = {
       semanticHighlighting : true,
     };
   }
 
   async loadCurrentTheme() {
     this.themeRuleMatcher = new ThemeRuleMatcher(
         await loadTheme(vscode.workspace.getConfiguration('workbench')
                             .get<string>('colorTheme')));
+    this.colorizer.updateThemeRuleMatcher(this.themeRuleMatcher);
   }
 
   initialize(capabilities: vscodelc.ServerCapabilities,
              documentSelector: vscodelc.DocumentSelector|undefined) {
     // The semantic highlighting capability information is in the capabilities
     // object but to access the data we must first extend the ServerCapabilities
     // type.
     const serverCapabilities: vscodelc.ServerCapabilities&
         {semanticHighlighting?: {scopes : string[][]}} = capabilities;
     if (!serverCapabilities.semanticHighlighting)
       return;
     this.scopeLookupTable = serverCapabilities.semanticHighlighting.scopes;
+    // Important that colorizer is created before the theme is loading as
+    // otherwise it could try to update the themeRuleMatcher without the
+    // colorizer being created.
+    this.colorizer =
+        new Colorizer<FileColorizer>(FileColorizer, this.scopeLookupTable);
     this.loadCurrentTheme();
   }
 
-  handleNotification(params: SemanticHighlightingParams) {}
+  handleNotification(params: SemanticHighlightingParams) {
+    const lines: SemanticHighlightingLine[] = params.lines.map(
+        (line) => ({line : line.line, tokens : decodeTokens(line.tokens)}));
+    this.colorizer.setFileLines(params.textDocument.uri, lines);
+  }
 }
 
 // Converts a string of base64 encoded tokens into the corresponding array of
 // HighlightingTokens.
 export function decodeTokens(tokens: string): SemanticHighlightingToken[] {
   const scopeMask = 0xFFFF;
   const lenShift = 0x10;
   const uint32Size = 4;
   const buf = Buffer.from(tokens, 'base64');
   const retTokens = [];
   for (let i = 0, end = buf.length / uint32Size; i < end; i += 2) {
     const start = buf.readUInt32BE(i * uint32Size);
     const lenKind = buf.readUInt32BE((i + 1) * uint32Size);
     const scopeIndex = lenKind & scopeMask;
     const len = lenKind >>> lenShift;
     retTokens.push({character : start, scopeIndex : scopeIndex, length : len});
   }
 
   return retTokens;
 }
 
+// A collection of ranges where all ranges should be decorated with the same
+// decoration.
+interface DecorationRangePair {
+  // The decoration to apply to the ranges.
+  decoration: vscode.TextEditorDecorationType;
+  // The ranges that should be decorated.
+  ranges: vscode.Range[];
+}
+// A simple interface of a class that applies decorations to make the Colorizer
+// to be testable.
+interface IFileColorizer {
+  // Function that is called whenever new decorations should be applied. Must be
+  // called with all decorations that should be visible in the TextEditor
+  // responsible for uriString currently.
+  colorize: (uriString: string,
+             decorationRangePairs: DecorationRangePair[]) => void;
+  // Called when any old decorations should be removed.
+  dispose: () => void;
+}
+// The main class responsible for colorization of highlightings that clangd
+// sends.
+export class Colorizer<T> {
+  private files: Map<string, Map<number, SemanticHighlightingLine>> = new Map();
+  private colorizers: Map<string, IFileColorizer> = new Map();
+  private themeRuleMatcher: ThemeRuleMatcher;
+  private scopeLookupTable: string[][];
+  private ColorizerType: {new(): IFileColorizer;};
+  constructor(ColorizerType: {new(): IFileColorizer;},
+              scopeLookupTable: string[][]) {
+    this.ColorizerType = ColorizerType;
+    this.scopeLookupTable = scopeLookupTable;
+  }
+  /// Update the themeRuleMatcher that is used when colorizing. Also triggers a
+  /// recolorization for all current colorizers.
+  public updateThemeRuleMatcher(themeRuleMatcher: ThemeRuleMatcher) {
+    this.themeRuleMatcher = themeRuleMatcher;
+    Array.from(this.colorizers.keys()).forEach((uri) => this.colorize(uri));
+  }
+
+  // Called when clangd sends an incremental update of highlightings.
+  public setFileLines(uriString: string, tokens: SemanticHighlightingLine[]) {
+    // Patch in the new highlightings to the highlightings cache. If this is the
+    // first time the file should be highlighted a new colorizer and a file
+    // container are created.
+    if (!this.files.has(uriString)) {
+      this.files.set(uriString, new Map());
+      this.colorizers.set(uriString, new this.ColorizerType());
+    }
+
+    const fileHighlightings = this.files.get(uriString);
+    tokens.forEach((line) => fileHighlightings.set(line.line, line));
+    this.colorize(uriString);
+  }
+
+  // Applies all highlightings to the file with uri uriString.
+  private colorize(uriString: string) {
+    if (!this.colorizers.has(uriString)) {
+      this.colorizers.set(uriString, new this.ColorizerType());
+    }
+
+    // Can't colorize if there is no matcher. When a matcher is set a
+    // colorization will be triggered. So it's ok to simply return here.
+    if (!this.themeRuleMatcher) {
+      return;
+    }
+    // This must always do a full re-colorization due to the fact that
+    // TextEditorDecorationType are very expensive to create (which makes
+    // incremental updates infeasible). For this reason one
+    // TextEditorDecorationType is used per scope.
+    // FIXME: It might be faster to cache the TextEditorDecorationTypes and only
+    // update the ranges for them.
+    const lines: SemanticHighlightingLine[] = [];
+    Array.from(this.files.get(uriString).values())
+        .forEach((line) => lines.push(line));
+    // Maps scopeIndexes -> the DecorationRangePair used for the scope.
+    const decorations: Map<number, DecorationRangePair> = new Map();
+    lines.forEach((line) => {
+      line.tokens.forEach((token) => {
+        if (!decorations.has(token.scopeIndex)) {
+          const options: vscode.DecorationRenderOptions = {
+            color : this.themeRuleMatcher
+                        .getBestThemeRule(
+                            this.scopeLookupTable[token.scopeIndex][0])
+                        .foreground,
+            // If the rangeBehavior is set to Open in any direction the
+            // colorization becomes weird in certain cases.
+            rangeBehavior : vscode.DecorationRangeBehavior.ClosedClosed,
+          };
+          decorations.set(token.scopeIndex, {
+            decoration : vscode.window.createTextEditorDecorationType(options),
+            ranges : []
+          });
+        }
+        decorations.get(token.scopeIndex)
+            .ranges.push(new vscode.Range(
+                new vscode.Position(line.line, token.character),
+                new vscode.Position(line.line,
+                                    token.character + token.length)));
+      });
+    });
+
+    this.colorizers.get(uriString).colorize(uriString,
+                                            Array.from(decorations.values()));
+  }
+}
+
+// Implementation of IFileColorizer to colorize text editors.
+class FileColorizer implements IFileColorizer {
+  // The decoration datatypes used last time a colorization was triggered.
+  private oldDecorations: DecorationRangePair[] = [];
+  // Apply decorations to the textEditor with uri.
+  public colorize(uri: string, decorationRangePairs: DecorationRangePair[]) {
+    vscode.window.visibleTextEditors.forEach((e) => {
+      if (e.document.uri.toString() !== uri) {
+        return;
+      }
+      decorationRangePairs.forEach(
+          (dp) => { e.setDecorations(dp.decoration, dp.ranges); });
+    });
+    // Clear the old decoration after the new ones have already been applied as
+    // otherwise there might be flicker.
+    this.dispose();
+    this.oldDecorations = decorationRangePairs;
+  }
+  public dispose() {
+    this.oldDecorations.forEach((decorations) =>
+                                    decorations.decoration.dispose());
+  }
+}
+
 // A rule for how to color TextMate scopes.
 interface TokenColorRule {
   // A TextMate scope that specifies the context of the token, e.g.
   // "entity.name.function.cpp".
   scope: string;
   // foreground is the color tokens of this scope should have.
   foreground: string;
 }

clang-tools-extra/clangd/clients/clangd-vscode/test/semantic-highlighting.test.ts

 import * as assert from 'assert';
 import * as path from 'path';
+import * as vscode from 'vscode';
 
 import * as SM from '../src/semantic-highlighting';
 
 suite('SemanticHighlighting Tests', () => {
   test('Parses arrays of textmate themes.', async () => {
     const themePath =
         path.join(__dirname, '../../test/assets/includeTheme.jsonc');
     const scopeColorRules = await SM.parseThemeFile(themePath);
test('ScopeRules overrides for more specific themes', () => {
     assert.deepEqual(
         tm.getBestThemeRule('storage'),
         rules[2]); // Match the first element if there are duplicates.
     assert.deepEqual(tm.getBestThemeRule('variable.other.parameter').scope,
                      'variable.other.parameter');
     assert.deepEqual(tm.getBestThemeRule('variable.other.parameter.cpp').scope,
                      'variable.other.parameter');
   });
+  test('Colorizer groups decorations correctly', () => {
+    const colorizations: {uri: string, decorations: any[]}[] = [];
+    // Mock of a colorizer that saves the parameters in the colorizations array.
+    class MockFileColorizer {
+      public colorize(uri: string, decorationRangePairs: any[]) {
+        colorizations.push({uri : uri, decorations : decorationRangePairs});
+      }
+      public dispose() {}
+    }
+    // Helper for creating a vscode Range.
+    const createRange = (line: number, startCharacter: number,
+                         length: number) =>
+        new vscode.Range(new vscode.Position(line, startCharacter),
+                         new vscode.Position(line, startCharacter + length));
+    const scopeTable = [
+      [ 'variable' ], [ 'entity.type.function' ],
+      [ 'entity.type.function.method' ]
+    ];
+    const rules = [
+      {scope : 'variable', foreground : '1'},
+      {scope : 'entity.type', foreground : '2'},
+    ];
+    const tm = new SM.ThemeRuleMatcher(rules);
+    const colorizer =
+        new SM.Colorizer<MockFileColorizer>(MockFileColorizer, scopeTable);
+    // No colorization if themeRuleMatcher has not been set.
+    colorizer.setFileLines('a', []);
+    assert.deepEqual(colorizations, []);
+    colorizer.updateThemeRuleMatcher(tm);
+    assert.deepEqual(colorizations, [ {decorations : [], uri : 'a'} ]);
+    // Groups decorations into the scopes used.
+    let line = [
+      {character : 1, length : 2, scopeIndex : 1},
+      {character : 5, length : 2, scopeIndex : 1},
+      {character : 10, length : 2, scopeIndex : 2}
+    ];
+    colorizer.setFileLines(
+        'a', [ {line : 1, tokens : line}, {line : 2, tokens : line} ]);
+    assert.equal(colorizations[1].uri, 'a');
+    assert.equal(colorizations[1].decorations.length, 2);
+    // Can't test the actual decorations as vscode does not seem to have an api
+    // for getting the actual decoration objects.
+    assert.deepEqual(colorizations[1].decorations[0].ranges, [
+      createRange(1, 1, 2), createRange(1, 5, 2), createRange(2, 1, 2),
+      createRange(2, 5, 2)
+    ]);
+    assert.deepEqual(colorizations[1].decorations[1].ranges,
+                     [ createRange(1, 10, 2), createRange(2, 10, 2) ]);
+    // Keeps state separate between files.
+    colorizer.setFileLines('b', [
+      {line : 1, tokens : [ {character : 1, length : 1, scopeIndex : 0} ]}
+    ]);
+    assert.equal(colorizations[2].uri, 'b');
+    assert.equal(colorizations[2].decorations.length, 1);
+    assert.deepEqual(colorizations[2].decorations[0].ranges,
+                     [ createRange(1, 1, 1) ]);
+    // Does full colorizations.
+    colorizer.setFileLines('a', [
+      {line : 1, tokens : [ {character : 2, length : 1, scopeIndex : 0} ]}
+    ]);
+    assert.equal(colorizations[3].uri, 'a');
+    assert.equal(colorizations[3].decorations.length, 3);
+    assert.deepEqual(colorizations[3].decorations[0].ranges,
+                     [ createRange(1, 2, 1) ]);
+    assert.deepEqual(colorizations[3].decorations[1].ranges,
+                     [ createRange(2, 1, 2), createRange(2, 5, 2) ]);
+    assert.deepEqual(colorizations[3].decorations[2].ranges,
+                     [ createRange(2, 10, 2) ]);
+  });
 });