Investigate into the performance issues of the bracket pair colorizer extension

[egamma]

Bracket Pair Colorizer is a very popular VS Code extension. However, users are reporting performance problems as the following tweet illustrates.

We should investigate into how the performance can be improved.

[IllusionMH]

Please note that there also is separate version Bracket Pair Colorizer 2 which should be faster, however lost some features around custom pairs.

[hediet]

@alexdima and I did some brainstorming.

The fundamental problem is to offer correct bracket highlighting while staying performant.

Consider the following TypeScript snippet:

function test() { [1]
    const str = `
        ${(() => { if (true) {  } })()}
    } [2]`;
} [3]

Does the bracket at [1] match with the bracket at [2] or at [3]?
To answer this question, the template literal expression before must be parsed correctly.
Unfortuantely, a single parsing inaccuracy might lead to erroneous matching of brackets for all later lines, degrading the entire experience.

Thus, perfect bracket pair colorization requires syntax tree information.

However, we think that the textmate tokens should be sufficient to identify matching bracket pairs, assuming the tokens are usually correct and that bracket pairs match if they have the same token type and the same level within all brackets of that token type. Simple matching is already implemented in the editor core. However, tokens are not always accurate, especially for long lines and for documents with many lines.

The goal should be to avoid iterating over the entire document on each keystroke to compute bracket colors.
This must also be avoided when rendering.

We identified the following possible solutions for implementing bracket pair colorizing:

1. Do Bracket Pair Colorizing Inside An Extension

• Con: The extension host must have access to tokens of a given document.
  Since VS Code textmate grammars can be extended by extensions and these extended grammars cannot be queried by extensions, the extension API needs to be extended for full support.
• Con: Exposing textmate tokens might cause a textmate lock-in. Moving away from textmate would then cause a breaking change.
• Con: If a document has thousands of bracket-pairs, there needs to be a way to efficiently update decorations. Alternatively, the extension only sends decorations for the current view port. It is a no go to update the decorations for all matching brackets on each keystroke.
• Pro: Extensions such as Blockman (13k installs) by @leodevbro, Rainbow Brackets by @Logicult (discontinued, 950k installs) or Rainbow Brackets 2 (2k installs) by @tejasvi might also benefit from this. It would be interesting to hear their opinions on this.

1.1. Expose Tokens To Extensions

• Pro: Extensions don't need to reimplement the textmate tokenizer.
• Con: Extensions expect the tokens to be correct. However, with the current state of textmate and due to some performance optimizations, we cannot guarantee correctness. However, we could restrict the token information to some very basic properties that are mostly correct.
• Con: We also cannot offer a fully synchronous way to access tokens, as this could block the extension host.

API usage could look like this:

const doc = vscode.workspace.textDocuments[0];

// If a non-undefined value is returned, these tokens must be in sync with `doc`.
// We intentionally don't return a promise here to avoid synchronization issues.
// This API allows to compute tokens in batches to avoid freezing the extension host.
const tokens: { isComputing: false, tokens: ILineToken[] } | { isComputing: true } = doc.getTokensForLine(myLine);

vscode.workspace.onDidChangeTextDocumentTokens((e: { changedRanges: Range[] }) => {
    // Is fired immediately after the text document got changed or computation started/finished.
    // Calls to `getTokensForLine` can still return `{ isComputing: true }`.
    const tokens = doc.getTokensForLine(myLine);
});

// Tokens itself could look like this:
interface ILineToken {
    kind: TokenKind,
    languageId: string, // e.g. 'typescript' or 'html'
    startOffset: number,
    endOffset: number
}

// Only provide a very limited amount of token kinds so that
// we don't expose too much textmate flavor.
// We could easily provide the same token information with tree-sitter or monarch.
enum TokenKind {
    default,
    string,
    comment,
    regex
}

There are various ways of how such an API could be implemented:

1.1.1. Send the Tokens Of The Renderer To The Extension Host

• Pro: The document only needs to be tokenized once.
• Con: Sending the tokens to the extension host could be very slow. At all costs, slowing down the renderer must be prevented. This is probably a blocker for this option.

1.1.2. Compute the Tokens In The Extension Host

• Con: Documents are tokenized twice.
• Con: Might slow down the extension host.

1.2. Compute the Tokens In The Extension

• Con: The extension needs to ship with recent grammars.
• Con: The extension needs to bundle oniguruma (by using webassembly)
• Con: The extension tokens and VS Code tokens might not align (an API would be needed for extensions to get a list of all registered textmate grammars, as extensions can contribute grammar extensions).
• Con: If implemented incorrectly, the extension could freeze the extension host (like Bracket Pair colorizer is doing).

1.a) Fix either Bracket Pair Colorizer 1 or 2

• Con: Both extensions by @CoenraadS are deprecated & the repositories are archived. There has not been a significant update for at least one year.
• Pro: No special steps required by the community to upgrade.

1.b) Create a New Extension

• Pro: A fresh start has the most opportunities to optimize for performance.
• Con: The community is important to us. Replacing popular community-extensions might be harmful and could discourage extension authors.

1.c) Wait for a New Extension by the Community + Provide Guidance

• Pro: We enable the community to support advanced customization options.
• Pro: With our guidance + potentially new API, we can help making this extension very performant

We could also start with 1.b) and encourage authors to fork our extension.

2. Implement Bracket Pair Colorizing Inside The Editor Core

• Pro: We can use the existing tokens without performance implications.
• Pro: We don't need to use decorations but can modify the rendering logic directly.
• Pro: We don't need to expose tokens to extensions, saving a lot of headaches.
• Con: We might exclude the community from customizing bracket pair colorization beyond what we offer.

---

Personally, I would love to do 1.1.2 + 1.c) (with 1.b as fallback and encouraging authors to fork).
However I think the fastest and least risky way to get performant Bracket Pair Colorization in VS Code would be option 2.

[CoenraadS]

Author of Bracket Pair Colorizer here.

I follow this thread with interest, my extension is something that grew a bit out of control, and I grew tired of maintaining it.

If there are some quick wins, I can still apply them, but I think my extension is so hacky it is easier to do 1.b or 1.c

I coded this thing when I was still in college and it shows 👎
Maybe the first step would be just to disable BC1, it's so bad yet people don't upgrade to BC2 (which still has it's own perf issues..)

[leodevbro]

Author of Blockman here.

1.1. Expose Tokens To Extensions

This was the first thing I was thinking when I started working on Blockman, and I think it's very natural idea, because why on earth would an extension re-parse/re-tokenize the file if the host already does it? Internal access to tokens would be super useful, if not all tokens, then at least the tokens which represent the opening and closing locations of each nested block.

Extensions expect the tokens to be correct. However, with the current state of textmate and due to some performance optimizations, we cannot guarantee correctness.

Well, maybe, if it's possible, the extension API should have access to the parsing process of host tokens with some option to choose between strict (maximally correct) mode and fast mode. I think maximum correctness must be always ON at least for the tokens which represent the opening and closing locations of each nested block.

We also cannot offer a fully synchronous way to access tokens, as this could block the extension host.

I think that's fine. Blockman gets brackets asynchronously and it seems to work fine for most of the users.

[hediet]

Thanks so much for reaching out! Your extensions not only make VS Code an even more amazing editor, but are also a source for inspiration!

If there are some quick wins, I can still apply them, but I think my extension is so hacky it is easier to do 1.b or 1.c

I had a quick look at your source, but I think a much more incremental data structures need to be adopted to get the desired performance - I doubt this is a low hanging fruit.
In particular, a single keystroke should not take more than O(log(Number of Lines)) steps to update this data structure (and in particular must not require to retokenize the entire file just for bracket colorization).

Maybe the first step would be just to disable BC1, it's so bad yet people don't upgrade to BC2 (which still has it's own perf issues..)

Did you experiment with notifications to inform users of BC2? When we have a more performant solution in place (however it may look), would you be open to help us getting users who struggle with BC2's performance to adopt that new solution?

because why on earth would an extension re-parse/re-tokenize the file if the host already does it?

The problem here is that at all costs we must prevent the renderer (who currently computes the tokens) from being slow. Synchronizing the tokens with the extension host could be slow, as the extension host is a separate process.

the tokens which represent the opening and closing locations of each nested block.

Unfortunately, the tokens produced by textmate grammars don't reflect blocks.

[leodevbro]

The problem here is that at all costs we must prevent the renderer (who currently computes the tokens) from being slow. Synchronizing the tokens with the extension host could be slow, as the extension host is a separate process.

Why not give the extension developers an option to access host tokens or not to access, so they can choose, they can test it for their specific case and maybe for some situations this approach will not be a deal breaker in terms of speed (even with async access).

Unfortunately, the tokens produced by textmate grammars don't reflect blocks.

What do you mean? Blockman uses the source code of Bracket Pair Colorizer 2 to find the locations of all brackets (which are by themselves the locations of block start and block end), and I believe BPC2 itself uses textmate, and so it provides all the locations (positions) of each bracket with this kind of array:

{
    char: string;
    type: number; // opening or closing
    inLineIndexZero: number;
    lineZero: number;
}[]

[hediet]

I believe BPC2 itself uses textmate, and so it provides all the locations (positions) of each bracket with this kind of array:

BC2 seems to postprocess the tokens.

and maybe for some situations this approach will not be a deal breaker in terms of speed

As an extension author myself I can fully understand you. However, from VS Code's perspective, slow extensions do not only degrade the experience of the extension itself, but of the entire product. This is already the case for BC2 - not only is bracket coloring slow for huge documents, but also all the TypeScript features.
This is why we don't want to give out API that can easily cause performance issues.

[jpcastberg]

I forked and made a minor edit about a month ago to debounce the tokenizations, was a major improvement for me with no noticeable change in responsiveness. https://github.com/jpcastberg/Performant-Bracket-Pair-Colorizer-2