Implement fuzzy file finder with keyboard shortcut `f`.
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 open a file
that fuzzily matches a given query.
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 techniqueis 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
- constructing the bloom filters may take a while on very large repositories. It's possible to work around this issue, but it's not implemented in this commit.
- the bloom filter algorithmm is sometimes more strict compared to the fuzzy finder in VS Code and IntelliJ. There are techniques to make the fuzzy finder more fuzzy, for example we could make all-lowercase queries case-insensitive. It's also worth consider whether we want scrap the bloom filters altogether and use an entirely different approach, for example by reusing techniques from nvim-telescope.
Demo: low-latency filtering in the chromium/chromium repository (~400k source files). Observe that negative results (0 matches) return instantly, this is a key-feature of the bloom-filter approach.
Demo: exact matches are highlighted differently from incomplete matches making it easier to visually parse the results
Demo: the intermediary page while the fuzzy finder is downloading filenames. For most repos with <20k source files, this step is usually instant. The result is cached for every repoName/commitID pair.
