Feature request: Heuristic orderless matching

[srithon]

Disclaimer: 3/4ths of the way through writing this issue, I realized that #205 was describing the same underlying request; however, I feel that my perspective is different enough to warrant another post. I apologize in advance if you disagree. Also, similar to #205, this is likely out of scope for being shipped directly with the package, and you may feel this is better suited as an external script.

---

In Emacs, there's a popular completion style package called orderless that acts as an alternative to traditional fuzzy matching. The idea is that the matching is done by tokenizing the input into multiple space-separated "components", similar to what's done in zoxide, except rather than requiring candidates to have the same order as the provided components (as in fuzzy matching), it essentially and's the matches of each pattern, yielding candidates that simply match all of the regexes, regardless of order; hence "orderless."

While this may initially seem a rather inefficient way of specifying your search criteria, after getting used to you quickly see its power. In real life, we often don't know exactly what order terms show up in, and using fuzzy matching would require you to manually reorder the terms in your search query to find what you are looking for.

For example, in Emacs, trying to discover the function org-insert-todo-heading-respect-content would be near impossible with traditional fuzzy matching, while with orderless, to figure out if such a function exists, you could simply use terms that describe what you want without worrying about the implementation-defined ordering in the name. In this particular example, I might search for something like org insert heading todo, and would then discover all of these relevant functions:

org-insert-todo-heading
org-insert-todo-subheading
org-insert-todo-heading-respect-content
evil-org-org-insert-todo-heading-respect-content-below

While admittedly the Emacs example is a bit contrived, at least in my experience this applies equally to filesystem structures as well. One particularly annoying tendency that I have with zoxide is that when trying to access dotfiles, I consistently find myself typing fish config rather than the config fish necessary to match ~/.config/fish. While this case could easily be handled explicitly, I feel that there exists a succinct heuristic algorithm which balances the power of the current, "unambiguous" approach to matching, while offering a notable usability improvement over the current algorithm- at least for myself.

Here's what I came up with so far:

• have a heuristic that balances the highest score with the "distance" from the user-provided ordering
  • essentially, if I say z fish config, ~/.config/fish would be high up there since it has a high score; thus it should override a directory that matches the ordering, but is used far less often like ~/Packages/fish/config
• if the provided terms are in the exact ordering, and adjacent terms show up in a directory path within k levels of one another (i.e with k = 1, foo/bar for the query foo bar), then boost the relative score compared to non-exact matches
  • rather than having a "strict" k, there would likely be a formula for boosting the score based on the value of k found in the input
  • this enables exact matches to be prioritized over non-exact matches, while hopefully acting as a good balance between both

In case this is out of scope and down the line I end up implementing this as an external script, I'll link the source under this issue in case anyone else wants the same thing.
Apart from that, thanks for your time, and for writing such an awesome package!