Quick pick filter freezes on queries with runs of * wildcards
- 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
Assessment
This issue has not been assessed yet.