Go back to substring filtering instead of fuzzy filteringuse-substring-filtering-instead-of-fuzzy

This reverts (more or less) what was done in b46623ebef, but makes it so that
you can search for multiple subwords by separating them with spaces. In my
opinion this gives us the best of both worlds: it provides much more relevant
filter results in general, but still allows to search for multiple substrings if
you don't know exactly how they occur in the item you are looking for.

In this commit we don't completely switch to substring matching: the default is
still fuzzy matching as before, but you can switch to substring matching on a
case-by-case basis by prefixing the filter string with "=". I don't think we
should keep this UX, but for now it makes it easy to do A/B testing of the two
mechanisms. (Note that it's not completely equivalent: if you want to search for
discontiguous substrings, you need to separate them with spaces when substring
matching, but you must _not_ use spaces when fuzzy matching.)

3 files changed, 71 insertions, 8 deletions

diff --git a/pkg/gui/context/filtered_list.go b/pkg/gui/context/filtered_list.go
index 13b9c166a..7e0dc9fcb 100644
--- a/pkg/gui/context/filtered_list.go
+++ b/pkg/gui/context/filtered_list.go
@@ -96,7 +96,7 @@ func (self *FilteredList[T]) applyFilter() {
 			getFilterFields: self.getFilterFields,
 		}
 
-		matches := fuzzy.FindFrom(self.filter, source)
+		matches := utils.FindFrom(self.filter, source)
 		self.filteredIndices = lo.Map(matches, func(match fuzzy.Match, _ int) int {
 			return match.Index
 		})
diff --git a/pkg/gui/controllers/helpers/suggestions_helper.go b/pkg/gui/controllers/helpers/suggestions_helper.go
index 2ae9d2158..21d0eca1c 100644
--- a/pkg/gui/controllers/helpers/suggestions_helper.go
+++ b/pkg/gui/controllers/helpers/suggestions_helper.go
@@ -3,6 +3,7 @@ package helpers
 import (
 	"fmt"
 	"os"
+	"strings"
 
 	"github.com/jesseduffield/gocui"
 	"github.com/jesseduffield/lazygit/pkg/commands/models"
@@ -128,13 +129,26 @@ func (self *SuggestionsHelper) GetFilePathSuggestionsFunc() func(string) []*type
 
 	return func(input string) []*types.Suggestion {
 		matchingNames := []string{}
-		_ = self.c.Model().FilesTrie.VisitFuzzy(patricia.Prefix(input), true, func(prefix patricia.Prefix, item patricia.Item, skipped int) error {
-			matchingNames = append(matchingNames, item.(string))
-			return nil
-		})
+		if strings.HasPrefix(input, "=") {
+			substrings := strings.Fields(input[1:])
+			_ = self.c.Model().FilesTrie.Visit(func(prefix patricia.Prefix, item patricia.Item) error {
+				for _, sub := range substrings {
+					if !utils.CaseAwareContains(item.(string), sub) {
+						return nil
+					}
+				}
+				matchingNames = append(matchingNames, item.(string))
+				return nil
+			})
+		} else {
+			_ = self.c.Model().FilesTrie.VisitFuzzy(patricia.Prefix(input), true, func(prefix patricia.Prefix, item patricia.Item, skipped int) error {
+				matchingNames = append(matchingNames, item.(string))
+				return nil
+			})
 
-		// doing another fuzzy search for good measure
-		matchingNames = utils.FuzzySearch(input, matchingNames)
+			// doing another fuzzy search for good measure
+			matchingNames = utils.FuzzySearch(input, matchingNames)
+		}
 
 		return matchesToSuggestions(matchingNames)
 	}
diff --git a/pkg/utils/search.go b/pkg/utils/search.go
index c204506f0..4b74c3a6c 100644
--- a/pkg/utils/search.go
+++ b/pkg/utils/search.go
@@ -13,7 +13,7 @@ func FuzzySearch(needle string, haystack []string) []string {
 		return []string{}
 	}
 
-	matches := fuzzy.Find(needle, haystack)
+	matches := Find(needle, haystack)
 	sort.Sort(matches)
 
 	return lo.Map(matches, func(match fuzzy.Match, _ int) string {
@@ -21,6 +21,55 @@ func FuzzySearch(needle string, haystack []string) []string {
 	})
 }
 
+// Duplicated from the fuzzy package because it's private there
+type stringSource []string
+
+func (ss stringSource) String(i int) string {
+	return ss[i]
+}
+
+func (ss stringSource) Len() int { return len(ss) }
+
+// Drop-in replacement for fuzzy.Find (except that it doesn't fill out
+// MatchedIndexes or Score, but we are not using these)
+func FindSubstrings(pattern string, data []string) fuzzy.Matches {
+	return FindSubstringsFrom(pattern, stringSource(data))
+}
+
+// Drop-in replacement for fuzzy.FindFrom (except that it doesn't fill out
+// MatchedIndexes or Score, but we are not using these)
+func FindSubstringsFrom(pattern string, data fuzzy.Source) fuzzy.Matches {
+	substrings := strings.Fields(pattern)
+	result := fuzzy.Matches{}
+
+outer:
+	for i := 0; i < data.Len(); i++ {
+		s := data.String(i)
+		for _, sub := range substrings {
+			if !CaseAwareContains(s, sub) {
+				continue outer
+			}
+		}
+		result = append(result, fuzzy.Match{Str: s, Index: i})
+	}
+
+	return result
+}
+
+func Find(pattern string, data []string) fuzzy.Matches {
+	if strings.HasPrefix(pattern, "=") {
+		return FindSubstrings(pattern[1:], data)
+	}
+	return fuzzy.Find(pattern, data)
+}
+
+func FindFrom(pattern string, data fuzzy.Source) fuzzy.Matches {
+	if strings.HasPrefix(pattern, "=") {
+		return FindSubstringsFrom(pattern[1:], data)
+	}
+	return fuzzy.FindFrom(pattern, data)
+}
+
 func CaseAwareContains(haystack, needle string) bool {
 	// if needle contains an uppercase letter, we'll do a case sensitive search
 	if ContainsUppercase(needle) {