Add fuzzy file finder with keyboard shortcut `t`.
Created by: olafurpg
Previously, there was no way to interactively search for a file that
matches a given fuzzy query. This commit adds a new modal that activates
on the keyboard shortcut t
and allows the user to quickly navigate to a file
with fuzzy searching.
The implementation in this commit is specifically designed to handle large repositories with >100k source files. The fuzzy finder achieves low-latency by:
- implementating all the filtering inside the browser on the client-side
- using bloom filters to quickly discard buckets of filenames that are guaranteed to not match a given query. This technique is used by the Scala language server and documented in this blog post https://scalameta.org/metals/blog/2019/01/22/bloom-filters.html
The downside of this approach:
- it can take a while to first download all filenames in the repository, especially for large repos like chromium/chromium. I'm not sure how to avoid this problem without doing the filtering on the server-side, which would add latency to every keystroke.
- the bloom filter algorithm is sometimes more strict compared to the fuzzy finder in VS Code and IntelliJ. There are techniques to make the fuzzy finder more fuzzy but they're not implemented in this PR. It's worth consider whether we want to use a different filtering algorithm in smaller repos (<50k source files) that allows more fuzzy queries.
Demo: low-latency filtering in the chromium/chromium repository (~400k source files). Most queries respond in <20ms, while a few outliers (in particular all-uppercase queries) can take ~200ms to respond.
Demo: indexing the filenames is non-blocking and the user can query against the partially indexed list of source files. This is only relevant for repos with >100k files. Indexing feels almost instant in repos like torvalds/linux (~76k files).
Demo: exact matches are highlighted in a slightly different color from incomplete matches making it easier to visually parse the results
Demo: by default, only the top 100 results are shown. It's optionally possible to expand the list of results.
Follow-up work on this PR is tracked in #21201 (closed).