Alternative matching algorithms (substring, subsequence, etc.) for completions

[xiaq]

Currently fish only supports prefix matching for completions. Consider these use cases:

1. $ ls
   very-long-prefix-001 very-long-prefix-002 very-long-prefix-003
   

   Substring matching (or more specifically suffix matching) would be useful in the above case.

$ ls
lorem-ipsum lorem-bar foo-ipsum foo-bar

zsh allows you to type l-i<Tab> and get lorem-ipsum. Like everything in zsh you have to do some mysterious configuration; in this case, you declare - as some type of separator valid in completions.

A more realistic example for the above use cases is package names - say you want to complete libreoffice-base, but both libreoffice and base match a lot of packages. However lib-b would almost certainly match libreoffice-base.

Although I found zsh helpful in case 2., there is still a case it doesn't cover - when components are joined without separators. Matching the string user typed as a subsequence can solve this problem. In the case of separator-delimited components, it can be almost as accurate as zsh's method, except that lib-b also matches libreoffice-l10n-br and liaaaab-aaa-b (the latter is invented, sorry).

[ridiculousfish]

Related to #528

[ridiculousfish]

Implemented as 908b075

The algorithms we support are (in order of preference):

1. Exact match - FOOBAR matches FOOBAR
2. Prefix match - FOO matches FOOBAR
3. Case insensitive exact match: foobar matches FOOBAR
4. Case insensitive prefix match - foo matches FOOBAR
5. Substring match: OOBA matches FOOBAR
6. Subsequence match: FBR matches FOOBAR

This works for tab completing files and executables, though not yet options.

[dag]

One little thing I've noticed is that if I try to complete a long option argument when fish has no completions for that command, the double hyphens expand to .oh-my-zsh which I happened to have in the same directory!

Perhaps the fuzzy matching could exclude hyphens.

[ghost]

It may be beneficial to try case-insensitive substring/subsequence matching as well.

[ridiculousfish]

95d5e55 addresses dag's issue by disabling fuzzy matching for file completions if the argument begins with a dash.

[krader1961]

It seems to me this has been addressed so closing.