Bracket pair parsing runs twice on keypress

[Tyriar]

Part of #161622

Bracket pair parsing appears to happen twice on a single keypress as it happens when content changes and when tokenization happens. Typically on simple input "cheap" tokenization runs in the same task:

Consider using a microtask to execute the parsing at the end of the task a single time (which may get deferred to later depending on the outcome of #163235), rather than eagerly during the content changed event. I haven't looked much at the code but could we do bracket matching more incrementally so it's not taking several milliseconds?

The impact of this running twice is that input latency is pushed out several milliseconds on lower end/average hardware.

[hediet]

On which document did you try this out?

The entire thing is 5.98ms, so it is 2% for me.

Also, it is by design that it reacts on both content changes and token changes - maybe it can be optimized, but I wouldn't call this a "bug".

I haven't looked much at the code but could we do bracket matching more incrementally so it's not taking several milliseconds?

Here is a description of the algorithm:
https://code.visualstudio.com/blogs/2021/09/29/bracket-pair-colorization

This section is about how incrementality is achieved:
https://code.visualstudio.com/blogs/2021/09/29/bracket-pair-colorization#_incremental-updates

Maybe there are some cheap optimizations that I missed though (e.g. getting rid of recursion).

[Tyriar]

On which document did you try this out?

I was mostly using InputHandler.ts from xterm.js or terminalInstance.ts from vscode yesterday.

The entire thing is 5.98ms, so it is 2% for me.

This is on your fast machine that is likely quite a ways off the average user (and the 50% below the average). I think for that screenshot I was using 4x CPU throttling on my main computer (Windows 11) to emphasise slow parts.

Also, it is by design that it reacts on both content changes and token changes - maybe it can be optimized, but I wouldn't call this a "bug".

Maybe I'm misunderstanding the incremental parsing, but if it's could do in less time what it does in content change after tokenization, it should be changed. To clarify, this is how I propose you solve it:

onContentChange(() => this._queueParse());
onTokenChange(() => this._queueParse());

_queued = false
_queueParse() {
  if (!this._queued) {
    queueMicrotask(() => this._parse());
    this.queued = true;
  }
}

That will make _parse run a single time at the end of the task (ie. before any rendering occurs).

Here is a description of the algorithm:
https://code.visualstudio.com/blogs/2021/09/29/bracket-pair-colorization

This section is about how incrementality is achieved:
https://code.visualstudio.com/blogs/2021/09/29/bracket-pair-colorization#_incremental-updates

Maybe there are some cheap optimizations that I missed though (e.g. getting rid of recursion).

What confused me a little is why it wasn't essentially instant when I was just typing a non-bracket character. I didn't look into how the algorithm works or dig very deep into the code as I'm sure you know what you're doing there, I'm more interested in ensuring it doesn't waste time running twice in a single task and whether this can be deferred to shortly after text is rendered.

[Tyriar]

Outcomes from our meeting:

• We probably can't defer this stuff as character changes next to brackets will shift the bracket decorations to the character to the left or right for example
• We could merge content and token change handlers into a single handler, we would just need to merge the ranges such that they don't overlap here:

vscode/src/vs/editor/common/model/bracketPairsTextModelPart/bracketPairsTree/bracketPairsTree.ts

Lines 85 to 113 in 00b54ae

	public handleDidChangeTokens({ ranges }: IModelTokensChangedEvent): void {
	const edits = ranges.map(r =>
	new TextEditInfo(
	toLength(r.fromLineNumber - 1, 0),
	toLength(r.toLineNumber, 0),
	toLength(r.toLineNumber - r.fromLineNumber + 1, 0)
	)
	);
	this.astWithTokens = this.parseDocumentFromTextBuffer(edits, this.astWithTokens, false);
	if (!this.initialAstWithoutTokens) {
	this.didChangeEmitter.fire();
	}
	}
	public handleContentChanged(change: IModelContentChangedEvent) {
	const edits = change.changes.map(c => {
	const range = Range.lift(c.range);
	return new TextEditInfo(
	positionToLength(range.getStartPosition()),
	positionToLength(range.getEndPosition()),
	lengthOfString(c.text)
	);
	}).reverse();
	this.astWithTokens = this.parseDocumentFromTextBuffer(edits, this.astWithTokens, false);
	if (this.initialAstWithoutTokens) {
	this.initialAstWithoutTokens = this.parseDocumentFromTextBuffer(edits, this.initialAstWithoutTokens, false);
	}
	}

• I'll set up a meeting for early next month to walk through the actual parsing code to see if we can come up with ideas to optimize

[hediet]

@Tyriar can you verify this issue?

[Tyriar]

I do see it happening twice on a single keypress, but one of them is delayed until stick scroll renders which occurs after provideInlineCompletions triggers another tokenization. So the problem I was pointing out that affects input latency is fixed 👌