Skip to content

Add fuzzy file finder with keyboard shortcut `t`.

Warren Gifford requested to merge olafurpg/fuzzy-modal into main

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:

  1. implementating all the filtering inside the browser on the client-side
  2. 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:

  1. 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.
  2. 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.

CleanShot 2021-05-16 at 13 15 53

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).

CleanShot 2021-05-16 at 12 38 50

Demo: exact matches are highlighted in a slightly different color from incomplete matches making it easier to visually parse the results

CleanShot 2021-05-16 at 13 23 37

Demo: by default, only the top 100 results are shown. It's optionally possible to expand the list of results.

CleanShot 2021-05-16 at 13 25 58

Follow-up work on this PR is tracked in #21201 (closed).

Merge request reports