Add builtin fuzzy support to browserpass #32

[sophacles]

This adds builtin support for fuzzy finding in the browserpass search bar. (Issue #32) It also adds options to:

1. Turn on/off the use of fuzzy search from the search bar.
2. Select which fuzzy finding algorithm to use.

The second option allows users to choose between:

• github.com/renstrom/fuzzysearch/fuzzy
• github.com/sahilm/fuzzy

NOTE: the selection of fuzzy algorithm should probably go away before merging the branch, but it is included right now, since there was a discussion on #209 about which of those algorithms would be right for browserpass. This makes switching between the two for evaluation simpler, until a decision can be made on which to include (or a decision to keep as-is).

[sophacles]

I've been running this on my machine - OSX/Chrome for about 1.5 weeks. I find the results of the sahilm/fuzzy package to be better as its ranking includes exact sub-matches in it's ranking, whereas the RankFind of renstrom/fuzzy only uses levenstein distance and is sometime non-intuitive.

Also note before this can be merged:

• [x] A decision on which algorithm to use should be reached
• [ ] Testing on Linux and windows should be done with Chrome
• [ ] Testing all OSes with firefox should be done.

[maximbaz]

This is awesome @sophacles!

I adore the selector for two fuzzy search libraries, such a cool idea 👍 I tested both, and I definitely agree with you, sahilm prioritizes exact sub-matches and that is intuitively what I want.

I didn't look into the code yet, but one thing you probably should do is add sort.Strings(result) in the end of every fuzzy search function in pass/disk.go, just like GlobSearch has. That way, sahilm's results begin to have on top exactly the same suggestions as GlobSearch in exactly the same order, and because of this we could even argue that it makes sense to enable fuzzy search by default - users that search for a certain substring will still see the same results on top, but they will see more results and that way will learn about the new feature of fuzzy search. No, that is completely false, this ignores the order computed by fuzzy search and is not what we want.

But then it's a little disappointing that those results that have exact sub-matches are not sorted, and people will notice the difference and be confused if we enable fuzzy search by default.

Exact sub-matches are important because when you open a URL and click on browserpass icon, the domain name will be searched (now with fuzzy search) and most likely only the credentials from this domain will be discovered, and it would be really nice if such "automatic domain name search" provided the same results in the same order in Glob and Fuzzy modes (if we want to enable fuzzy search by default).

For example, when I open github.com and click on browserpass, with Glob I had:

personal/github.com
work/github.com

With sahilm fuzzy search I have now:

work/github.com
personal/github.com

My muscle memory is already used to hit TabEnter to login with personal github, now I will suddenly login with work account... 🤔

---

I'll continue using this PR for a few days to give it a longer test run, but since both of us agree that sahilm library is the way to go, feel free to remove the other one from PR now.

[maximbaz]

Looking at the code of sahilm/fuzzy I see that this is their fundamental property, matches earlier in the string win. In my example, github.com in string work/github.com begins to match since index 4, while in string personal/github.com it begins to match only since index 8, therefore work/github.com ranks first.

[maximbaz]

I found one issue:

Create domain.com.gpg in your .password-store, go to sub.domain.com in the browser, click on browserpass icon.

With glob search, domain.com will be discovered, with fuzzy search it is not discovered.

I think there is some code in GlobSearch that unwraps the query string (in this case sub.domain.com) into parent domains, perhaps it's not happening with fuzzy search.

[sophacles]

@maximbaz Good catch on that subdomain issue!

I think its all the way fixed now. I solved it by adding a new action called match_domain in the communication between the plugin and the native client. The handling for this will use glob search always, while normal user entered search will use whichever method is in the settings.

I also removed the renstrom algorithm, and the settings for fuzzy algorithm selection.

[maximbaz]

This sounds like a reasonable approach 👍 I'll keep testing and will also review code later today.

[sophacles]

@maximbaz - thanks for the review. I have pushed up some changes addressing your comments so far.

[sophacles]

@maximbaz re testing: I can whip up some tests for the golang part tonight (and maybe over the next couple days depending on how much learning I need to do :) ).

For the plugin side though - I have no idea how to do tests for a plugin, and don't see any existing already to build from... Any pointers?

[maximbaz]

There are no tests for browser extension part, but it's supposed to be a thin client anyway, with most logic in the host app. Just do the pass/disk_test.go and that's enough 😉

[maximbaz]

A friendly ping @sophacles 🙂

[sophacles]

@maximbaz - sorry about that! Got tied up with $DAYJOB things and this slipped my mind.

Just checked in some tests for the pass module! Not sure how to go about doing testing on the changes I've made to browserpass.go - input?

[maximbaz]

Thanks a lot! I think this is enough, we will live with manual tests for browserpass.go for now, I'm mainly concerned with keeping regressions away from searching and matching functionality.

Also, I have been using this branch on a daily basis since you created this PR, and I did not have any issues.

I'm going to merge this now and release a new versions - I'm keen to get users' feedback since fuzzy search will be enabled by default 😉