Support fuzzy search in HTML reporter's module filter

[ventuno]

The HTML reporter's "module filter" uses String.indexOf() to filter the list of modules.
This works well in general, but can be annoying as the list of modules gets longer and module names contain special characters. For example, if a module name is written in kebab case: my-module-something the user needs to input all -s in order to find the module in the list.
It would be a better user experience to filter the list based on approximate string matching (or fuzzy search) instead.

I'd be more than happy to take this up myself, but first I'd like to know if this feature could be interesting and the below approach seems reasonable.

Recommended implementation

This change could be implemented in two steps:

1. Modify the way the list of modules is rendered and filtered;
2. Change the search algorithm to use fuzzy search.

1) Modify the way the list of modules is rendered and filtered

This first set of changes is crucial to successfully implement the second step.
Here's how the modules filter is currently built and operated:

1. The list of modules is built once in moduleListHtml. This function does not take any argument, but simply reads the list of modules in config.modules;
2. The list is filtered in searchInput, this method identifies the which modules to hide and show as outlined above and uses CSS (display: none) to hide list items.

Here's a list of changes required for the next step:

1. If we are going to use fuzzy search, we can expect the filtered modules list to change not only in the number of elements, but also their relative ordering. Fuzzy search ranks search results, this means that the order of modules will change as the query changes. In order to do this moduleListHtml will have to take a list of modules to render instead of simply render the entire list of modules;
2. searchInput should rely on some external module (see below) to filter the list of modules, then it will have to re-render the list of modules instead of simply hiding/showing individual list items. Depending on the size of the list of modules, this approach could make the UI slow. It is recommended to apply thorough testing and debounce each call to searchInput in order to reduce the amount of re-renders required.

Sample implementation

#1439

2) Change the search algorithm to use fuzzy search

Once the above step is complete, it becomes trivial to implement this step, as the only thing to do is changing the filtering function.
Here's a list of candidate modules I identified to implement fuzzy search:

• Fuse.js is a fuzzy-search library;
• fuzzysort is a SublimeText-like fuzzy search library;
• natural is a general natural language facility for nodejs. It implements approximate string matching.

I did some testing with all of them with a ~900 list of modules and my recommended approach would be to use Fuse.js or fuzzysort. I exclude natural because it is a large library that does a lot more than just fuzzy search. This library offers a LevenshteinDistance method, but doesn't offer a method to rank searches like Fuse.js and fuzzysort.

fuzzysort doesn't seem to be under active development. The last commit (at the time I'm writing this) dates > 2 years ago. fuzzysort (very subjective) seemed to return the "best" set of results.

Fuse.js seems to be under active development with the last commit 4 days ago (at the time I'm writing this) and a pretty frequent release history.

I didn't do any performance testing on these libraries, I'd be happy to know if the community knows the number of modules the HTML reporter is expected to support, this would help understanding if a serious performance analysis is required.

Sample implementation

Each PR below contains a set of screenshots for the same keyword search with both libraries.

• fuzzysort: HTML Reporter: Fuzzy search using fuzzysort #1440;
• Fuse.js: WIP HTML Reporter: Fuzzy search using fuse #1442 WIP HTML Reporter: Fuzzy search using fuse #1441.

[ventuno]

@trentmwillis thoughts?

[trentmwillis]

This seems like a good feature to me. Thanks for working on it. I'll review the various PRs.

[trentmwillis]

This has been implemented using fuzzysort (#1440)