refactor of the fuzzy_nucleo string and path matching code, instead of
handling the multiple atoms ourselves we can just use `nucleo::Pattern`
and abstract that all away. this replaces the for loop in the
path/string_match_helper functions. all functionality is exactly the
same. basically the same / within some tiny margin of the original.
this could enable the use of `nucleo::Pattern::parse` in the future if
that was wanted, which allows some extra syntax to activate different
matching modes. [more info from
deepwiki](https://deepwiki.com/search/how-do-the-different-atom-matc_37e510de-af27-44a1-a52f-3fc367462e6e?mode=fast).
I'm pretty sure that enabling that is as simple as switching a
`Pattern::new(...)` call with `Pattern::parse(...)`.
Self-Review Checklist:
- [x] I've reviewed my own diff for quality, security, and reliability
- [x] Unsafe blocks (if any) have justifying comments
- [x] The content is consistent with the [UI/UX
checklist](https://github.com/zed-industries/zed/blob/main/CONTRIBUTING.md#uiux-checklist)
- [x] Tests cover the new/changed behavior
- [x] Performance impact has been considered and is acceptable
Release Notes:
- N/A
Closes ZED-6PK
The issue here was that we could hit cases where the amount of segments
< amount of CPUs, e.g. for 5 candidates and 4 CPUs, we would have 2
candidates per matcher, so for the fourth matcher, we would start
slicing at 3 * 2 = 6 > 5, which is out of bounds.
Instead, make it so that we distribute the candidates across all
matchers so that all matchers have either n or n + 1 candidates.
No release notes since this is only on Nightly.
Release Notes:
- N/A
Stacked on top of #54112
This is part 2 of 3 towards #51197
More details from the original PR #53551
This PR includes the changes from #54112 , im not sure how to avoid
that, my understanding is that after that one is merged, this PR can be
rebased onto main and everything will be correct. You can also view the
version of this that does reflect the changes more directly here:
https://github.com/feitreim/zed/pull/1
## Changes
In this PR I added a more general string matching functionality to
`fuzzy_nucleo`, in order to have proper testing for this, I also changed
the command palette, tab switching picker, branch picker, and recent
projects picker to use this new implementation. I think the command
palette change in particular is awesome, just super nice to vaguely
gesture at the command i want and have it pop right up.
The main change here and departure from
https://github.com/zed-industries/zed/pull/37123 is realizing that the
primary reason for the regressions is actually how nucleo handles smart
case, the old `fuzzy` crate only uses the smart case argument to score
things differently, while nucleo actually filters on the case, eg. with
smart case query "Apple" wouldnt match "apple". To get around this we
always pass `CaseMatching::Ignore` to nucleo and implement the same
score modifications from fuzzy in our code.
There is a performance cost to that, of course, but from my testing it
is fairly static, not growing as the size increases, so maybe a query
takes 35 µs instead of 25 µs, but a query that takes 800 µs will only
take 820 µs.
Benchmark:
| kind | query | size | nucleo | fuzzy | nucleo/fuzzy |
|---|---|---:|---:|---:|---:|
| string | 1-word | 100 | 9.15 µs | 24.6 µs | 0.37× |
| string | 1-word | 1000 | 150.2 µs | 207.2 µs | 0.72× |
| string | 1-word | 10000 | 1.34 ms | 2.07 ms | 0.65× |
| string | 2-word | 100 | 5.16 µs | 2.94 µs | 1.75× |
| string | 2-word | 1000 | 29.0 µs | 11.0 µs | 2.63× |
| string | 2-word | 10000 | 210.6 µs | 55.5 µs | 3.79× |
| string | 4-word | 100 | 2.57 µs | 2.33 µs | 1.10× |
| string | 4-word | 1000 | 6.98 µs | 5.85 µs | 1.19× |
| string | 4-word | 10000 | 20.0 µs | 12.0 µs | 1.66× |
When I added the 4-word queries to the benchmarks I was actually really
concerned that the performance would be awful, making it unsuitable for
the command palette especially. However, I think due to the CharBag
pre-filtering when the query is longer, the performance is actually way
better than the 2 word case.
Video:
https://github.com/user-attachments/assets/3cd7221b-424f-4fd3-8df1-5543dcc340a3
Self-Review Checklist:
- [x] I've reviewed my own diff for quality, security, and reliability
- [x] Unsafe blocks (if any) have justifying comments
- [x] The content is consistent with the [UI/UX
checklist](https://github.com/zed-industries/zed/blob/main/CONTRIBUTING.md#uiux-checklist)
- [x] Tests cover the new/changed behavior
- [x] Performance impact has been considered and is acceptable
Release Notes:
- Improved fuzzy matching in the command palette, branch picker, tab
switcher, and recent projects picker to support multi-word queries.
---------
Co-authored-by: Yara <git@yara.blue>
Closes#14428
Before you mark this PR as ready for review, make sure that you have:
- [ ] Added a solid test coverage and/or screenshots from doing manual
testing
https://github.com/user-attachments/assets/7e0d67ff-cc4e-4609-880d-5c1794c64dcf
- [x] Done a self-review taking into account security and performance
aspects
- [x] Aligned any UI changes with the [UI
checklist](https://github.com/zed-industries/zed/blob/main/CONTRIBUTING.md#uiux-checklist)
Release Notes:
- Adds a new `fuzzy_nucleo` crate that implements order independent path
matching using the `nucleo` library. currently integrated for file
finder.
---------
Signed-off-by: Bhuminjay <bhuminjaysoni@gmail.com>
Signed-off-by: 11happy <soni5happy@gmail.com>
