From b46623ebef3c897e0bb20bd4dcdd0832b349f2af Mon Sep 17 00:00:00 2001
From: Jesse Duffield <jessedduffield@gmail.com>
Date: Sat, 22 Jul 2023 13:04:39 +1000
Subject: Use fuzzy search when filtering a view

This adds fuzzy filtering instead of exact match filtering, which is more forgiving of typos
and allows more efficiency.
---
 pkg/gui/context/filtered_list.go                   | 39 +++++++++++++++-------
 pkg/integration/components/view_driver.go          |  1 +
 .../tests/filter_and_search/filter_fuzzy.go        | 35 +++++++++++++++++++
 pkg/integration/tests/test_list.go                 |  1 +
 4 files changed, 64 insertions(+), 12 deletions(-)
 create mode 100644 pkg/integration/tests/filter_and_search/filter_fuzzy.go

diff --git a/pkg/gui/context/filtered_list.go b/pkg/gui/context/filtered_list.go
index 298d3d615..d2361ad53 100644
--- a/pkg/gui/context/filtered_list.go
+++ b/pkg/gui/context/filtered_list.go
@@ -1,7 +1,11 @@
 package context
 
 import (
+	"strings"
+
 	"github.com/jesseduffield/lazygit/pkg/utils"
+	"github.com/sahilm/fuzzy"
+	"github.com/samber/lo"
 	"github.com/sasha-s/go-deadlock"
 )
 
@@ -53,6 +57,21 @@ func (self *FilteredList[T]) UnfilteredLen() int {
 	return len(self.getList())
 }
 
+type fuzzySource[T any] struct {
+	list            []T
+	getFilterFields func(T) []string
+}
+
+var _ fuzzy.Source = &fuzzySource[string]{}
+
+func (self *fuzzySource[T]) String(i int) string {
+	return strings.Join(self.getFilterFields(self.list[i]), " ")
+}
+
+func (self *fuzzySource[T]) Len() int {
+	return len(self.list)
+}
+
 func (self *FilteredList[T]) applyFilter() {
 	self.mutex.Lock()
 	defer self.mutex.Unlock()
@@ -60,20 +79,16 @@ func (self *FilteredList[T]) applyFilter() {
 	if self.filter == "" {
 		self.filteredIndices = nil
 	} else {
-		self.filteredIndices = []int{}
-		for i, item := range self.getList() {
-			for _, field := range self.getFilterFields(item) {
-				if self.match(field, self.filter) {
-					self.filteredIndices = append(self.filteredIndices, i)
-					break
-				}
-			}
+		source := &fuzzySource[T]{
+			list:            self.getList(),
+			getFilterFields: self.getFilterFields,
 		}
-	}
-}
 
-func (self *FilteredList[T]) match(haystack string, needle string) bool {
-	return utils.CaseAwareContains(haystack, needle)
+		matches := fuzzy.FindFrom(self.filter, source)
+		self.filteredIndices = lo.Map(matches, func(match fuzzy.Match, _ int) int {
+			return match.Index
+		})
+	}
 }
 
 func (self *FilteredList[T]) UnfilteredIndex(index int) int {
diff --git a/pkg/integration/components/view_driver.go b/pkg/integration/components/view_driver.go
index d1d1571c7..d3216bb91 100644
--- a/pkg/integration/components/view_driver.go
+++ b/pkg/integration/components/view_driver.go
@@ -539,6 +539,7 @@ func (self *ViewDriver) FilterOrSearch(text string) *ViewDriver {
 	self.Press(self.t.keys.Universal.StartSearch).
 		Tap(func() {
 			self.t.ExpectSearch().
+				Clear().
 				Type(text).
 				Confirm()
 
diff --git a/pkg/integration/tests/filter_and_search/filter_fuzzy.go b/pkg/integration/tests/filter_and_search/filter_fuzzy.go
new file mode 100644
index 000000000..198020afa
--- /dev/null
+++ b/pkg/integration/tests/filter_and_search/filter_fuzzy.go
@@ -0,0 +1,35 @@
+package filter_and_search
+
+import (
+	"github.com/jesseduffield/lazygit/pkg/config"
+	. "github.com/jesseduffield/lazygit/pkg/integration/components"
+)
+
+var FilterFuzzy = NewIntegrationTest(NewIntegrationTestArgs{
+	Description:  "Verify that fuzzy filtering works (not just exact matches)",
+	ExtraCmdArgs: []string{},
+	Skip:         false,
+	SetupConfig:  func(config *config.AppConfig) {},
+	SetupRepo: func(shell *Shell) {
+		shell.NewBranch("this-is-my-branch")
+		shell.EmptyCommit("first commit")
+		shell.NewBranch("other-branch")
+	},
+	Run: func(t *TestDriver, keys config.KeybindingConfig) {
+		t.Views().Branches().
+			Focus().
+			Lines(
+				Contains(`other-branch`).IsSelected(),
+				Contains(`this-is-my-branch`),
+			).
+			FilterOrSearch("timb"). // using first letters of words
+			Lines(
+				Contains(`this-is-my-branch`).IsSelected(),
+			).
+			FilterOrSearch("brnch"). // allows missing letter
+			Lines(
+				Contains(`other-branch`).IsSelected(),
+				Contains(`this-is-my-branch`),
+			)
+	},
+})
diff --git a/pkg/integration/tests/test_list.go b/pkg/integration/tests/test_list.go
index 5eab827b7..aa43dd2c1 100644
--- a/pkg/integration/tests/test_list.go
+++ b/pkg/integration/tests/test_list.go
@@ -98,6 +98,7 @@ var tests = []*components.IntegrationTest{
 	file.RememberCommitMessageAfterFail,
 	filter_and_search.FilterCommitFiles,
 	filter_and_search.FilterFiles,
+	filter_and_search.FilterFuzzy,
 	filter_and_search.FilterMenu,
 	filter_and_search.FilterRemoteBranches,
 	filter_and_search.NestedFilter,
-- 
cgit v1.2.3