microsoft / microsoft/vscode

Quick pick filter freezes on queries with runs of * wildcards

Open
#332,507 0 comments 0 reactions 1 assignee Claimed by @TylerLeonhardt View on GitHub
Dominant language
TypeScript
Stars
193k
Forks
42.4k
PR merge metrics
PR metrics pending

Description

### Bug description

`matchesFuzzy` (src/vs/base/common/filters.ts) supports `*` wildcards in quick pick queries by converting the query with `strings.convertSimple2RegExpPattern`, which replaces every `*` with its own `.*`. A query containing a run of adjacent stars therefore produces N adjacent unbounded quantifiers, and matching becomes super-polynomial: the regexp engine explores every composition of the haystack across the wildcards before failing near the end.

Measured on this machine against the real compiled module:

- `matchesFuzzy('********b', 'a'.repeat(28))`: about 1.4 seconds
- 12 stars against 40 characters: over two minutes
- simulated 20,000 label picker with query `*****com`: about 2.5 seconds per keystroke

This freezes the renderer while typing in any quick access that routes through `matchesFuzzy` (views, commands-adjacent pickers, debug pickers, icon labels).

### Steps to reproduce

1. Open a quick input that filters with fuzzy matching.
2. Type several `*` characters in a row followed by a letter that does not match, e.g. `********z`.
3. Observe input latency grow combinatorially with each additional star.

### Expected behavior

Adjacent wildcards should behave like a single wildcard. Collapsing runs of `*` to one `*` leaves the matched language identical (`.*.*` accepts exactly what `.*` does) and removes this class of hang entirely; measured to under a millisecond for the cases above after the change.

### Version tested

Commit `77f86f3d3a0` on `main`. Note a second, related backtracking surface remains open afterwards: many *separated* wildcards (`a*b*c*d*e*f*g*h`) can still backtrack exponentially on adversarial labels. The regex path has no length cap today, unlike the `fuzzyScore` path which caps at `_maxLen = 128`; that deserves its own discussion.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.