Feature Request: Fuzzy Search

[iliazlobin]

An innate feature to search through the Terminal text is quite limited and basic:

• it doesn't highlight several entries in the window;
• it doesn't support using regular expressions;
• it can't filter output to a fewer number of lines (much like grep does).
• it only supports strict match;

With the power of fuzzy search, users gain a boost to their productivity of being able to find a text through history very fast. It's implemented in many text editors (JetBrains IDEA, Visual Studio Code) for their project's files search. There's a solution specifically for the command line (bash/zsh) as well - junegunn/fzf.

If we could integrate the feature into the terminal (via its UI) without relying on the bash settings, it would be a great capability!

[zadjii-msft]

Thanks for the suggestion! There are certainly parts of your request that are already being tracked in #3920, but I'll use this issue to specifically track implementing "fuzzy search". Thanks!

[zadjii-msft]

@lhecker Just a thought scrolling through the backlog: how hard is this (fzf like search in terminal) now that we've got #15858?

Could we just (behind the scenes) convert something like foo into \b.*?f.*?o.*?o.*?\b? (I'm sure there's a better regex)

[lhecker]

Hmm, I'm not sure. A fuzzy matcher would sort results by their closeness to the needle. That would mean we would need to still implement a different searcher to rank them. fzf uses a variant of the Smith–Waterman algorithm which we could implement as well. I think something like that would be a requirement for this issue.

But I think #15858 is still helpful for this issue. Since it presents a view into the TextBuffer as if it was a single contiguous string, and because it provides facilities to map character positions back to row/column indices, we can now implement such string search algorithms much easier now.
ICU offers utext based APIs like UTEXT_NEXT32 to return the next UTF-32 character, u_foldCase to turn it into a consistent casing and then we can just feed it into the Smith–Waterman algorithm. Alternatively there's also grapheme cluster iterators, etc.