Consider prioritizing matches on filenames

[reykjalin]

I'm primarily familiar with nucleo through Helix and one paper-cut I experience every time in codebases with a larger-than-average number of files in them is that the fuzzy finder for files isn't all that great when trying to find a file that shares some part of its name with a directory.

However, the opposite is true when I use https://github.com/natecraddock/zf, which has a matching algorithm that prioritizes matches on filenames, and I find that it's much easier to find the files I'm looking for when there's some ambiguity between directories and filenames.

Here are 2 examples where this comes into play that were easy for me to think up on the spot:

Helix	zf

This may not be a good general approach for a fuzzy finder, but when searching for files specifically I think it's a big improvement.

Obviously this isn't a huge issue, and I don't think it's worth it to change the general matching algorithm. But if it's possible to add a separate matching function, or add a parameter or something to indicate that you are matching file names, maybe that's worth considering?

I think it would certainly improve the helix file picker at least, even if it's already mostly great.

[pascalkuthe]

with regquests like this it's always a question of what prioritize means: Is that a tie breaker? Does it tie into the scoring? If so how much to increase the score (eg. you searched for foobar and there is foobar/baz.rs and baz/foo_bar.rs which one to prioritize). As there is prior art with zf you could look at what they do. Or is your complain just about which indices we highlight (in case they all have the same score anyway) in that case there is probably a small tweak to make somewhere to prioritize later matches

[reykjalin]

Hey, thanks for replying so quickly!

I just want to start off saying that I understand nucleo explicitly aims to perfectly match fzf's scoring system. I'm not asking you to pivot from that, which is why I started this as a discussion, and not an issue. There is no problem with the implementation of nucleo to the best of my knowledge.

I did want to point out alternative scoring systems for file names that I have personally found to be better, in case there was interest on your side to add support for more scoring systems, or add support for tweaking the scoring system for specific use cases.

With that said, I'll reply to your comment:

it's always a question of what prioritize means: Is that a tie breaker? Does it tie into the scoring? If so how much to increase the score
[…]
there is prior art with zf you could look at what they do

I'm not sure how zf does this. I know nothing about the implementation details for nucleo or zf, but could look into zf a bit. Based on the zf readme I think they literally run the query first against the filename, and only try to match the rest of the path if the filename doesn't match:

The query is matched first on the filename and then on the path if the filename doesn't match
Source

I don't know what counts as "not matching" in terms of the scoring system zf uses, but my understanding of the writing is that "not matching" is only a thing when the score is 0, i.e. literally no match.

Nathan also has a couple articles on his blog about zf. Creating a better file finder describes the algorithm like so:

1. Split the query string into whitespace-separated tokens.
2. For each file path, compare the basename of the path with the first token. If there is no match the path is discarded.
3. Any remaining tokens are matched against the full string of any remaining paths. If any don’t match, the path is discarded.
4. If there are no results, begin matching with tokens again against the entire path, rather than against the basename only.

And In search of a better file finder has some interesting statistics on file names in a couple open source codebases, if you're interested.

---

is your complain just about which indices we highlight

No, the current highlights are great. I'm thinking about how the matches are ranked — and thus sorted — in the final results. I think the utilities search example in my original post demonstrates this best. Getting all the files called utilities instead of directories with utilities in their path names is something I personally consider a better match when searching for files.

[pascalkuthe]

I am not completely fixed on matching fzf if better options comeup but I found fzf to usually be really good so that is why I aimed to match it. Taking a galcne at the implementation in zf and they really simply try matching each atom on the filename first and if it matches give a 2x boost to rank/score. Unfortunaetly their ranking system is not really comperable to ours. It's less sophisticated (not really fuzzy more of a lenient substrings search) so it's not really comperable.

I think what nucleo could experiment with is having a bonus for matches that start (and logically end) in the filename. We already have some special handling for paths (treating / as a seperator). That should integrate reasonbly into the current scoring system (by making it a start bonus that should avoid issues where the algorithm introduces weird gaps to get the bonus).

I am currently focused on other things and genreally way too busy but maybe or you or someone else interested in contributing on it could work on it. Before I merge such a PR I would like to see a decent set of examples/tests showing both benefits and trying to find cases where it might perform wores and either showing it doesn't get worse or atleast arguing why that is an ok tradeoff in that case

[reykjalin]

That all makes sense! I'm busy myself and don't think I'll have time for this. That said I'll keep this in the back of my mind and if the itch gets bad enough I'll see if I can't open a PR to explore this somewhat :)

And I'll stay subscribed to this discussion too just in case someone else decides to pick this up. I'm happy to help with testing and such as much as I'm able 👍

Really appreciate your time here, thanks! ❤️

[FelipeLema]

due noting that fzf does "tiebreak for prioritizing matches occurring in the tail element of a file path" with --scheme=path / --tiebreak=pathname,length in junegunn/fzf#4192

even if it's not exactly zf's "basename matching", it works excellent as an alternative (at least for me)