commands: implement fuzzy completion for commands and options

Change the option to enable fuzzy completion to be fuzzy-complete, since
it's no longer only used for folders

Signed-off-by: Kt Programs <ktprograms@gmail.com>
Acked-by: Koni Marti <koni.marti@gmail.com>

12 files changed, 90 insertions, 78 deletions

diff --git a/commands/account/recover.go b/commands/account/recover.go
index a167d500..855d9846 100644
--- a/commands/account/recover.go
+++ b/commands/account/recover.go
@@ -6,8 +6,8 @@ import (
 	"io/ioutil"
 	"os"
 	"path/filepath"
-	"strings"
 
+	"git.sr.ht/~rjarry/aerc/commands"
 	"git.sr.ht/~rjarry/aerc/models"
 	"git.sr.ht/~rjarry/aerc/widgets"
 	"git.sr.ht/~sircmpwn/getopt"
@@ -24,24 +24,43 @@ func (Recover) Aliases() []string {
 }
 
 func (Recover) Complete(aerc *widgets.Aerc, args []string) []string {
+	acct := aerc.SelectedAccount()
+	if acct == nil {
+		return make([]string, 0)
+	}
+
 	// file name of temp file is hard-coded in the NewComposer() function
 	files, err := filepath.Glob(
 		filepath.Join(os.TempDir(), "aerc-compose-*.eml"),
 	)
 	if err != nil {
-		return []string{}
+		return make([]string, 0)
+	}
+	// if nothing is entered yet, return all files
+	if len(args) == 0 {
+		return files
 	}
-	arg := strings.Join(args, " ")
-	if arg != "" {
-		for i, file := range files {
-			files[i] = strings.Join([]string{arg, file}, " ")
+	if args[0] == "-" {
+		return []string{"-f"}
+	} else if args[0] == "-f" {
+		if len(args) == 1 {
+			for i, file := range files {
+				files[i] = args[0] + " " + file
+			}
+			return files
+		} else {
+			// only accepts one file to recover
+			return commands.FilterList(files, args[1], args[0]+" ", acct.UiConfig().FuzzyComplete)
 		}
+	} else {
+		// only accepts one file to recover
+		return commands.FilterList(files, args[0], "", acct.UiConfig().FuzzyComplete)
 	}
-	return files
 }
 
 func (Recover) Execute(aerc *widgets.Aerc, args []string) error {
-	if len(Recover{}.Complete(aerc, args)) == 0 {
+	// Complete() expects to be passed only the arguments, not including the command name
+	if len(Recover{}.Complete(aerc, args[1:])) == 0 {
 		return errors.New("No messages to recover.")
 	}
 
diff --git a/commands/account/sort.go b/commands/account/sort.go
index 89a5e386..15ecbc0c 100644
--- a/commands/account/sort.go
+++ b/commands/account/sort.go
@@ -4,6 +4,7 @@ import (
 	"errors"
 	"strings"
 
+	"git.sr.ht/~rjarry/aerc/commands"
 	"git.sr.ht/~rjarry/aerc/lib/sort"
 	"git.sr.ht/~rjarry/aerc/widgets"
 )
@@ -19,6 +20,11 @@ func (Sort) Aliases() []string {
 }
 
 func (Sort) Complete(aerc *widgets.Aerc, args []string) []string {
+	acct := aerc.SelectedAccount()
+	if acct == nil {
+		return make([]string, 0)
+	}
+
 	supportedCriteria := []string{
 		"arrival",
 		"cc",
@@ -35,7 +41,7 @@ func (Sort) Complete(aerc *widgets.Aerc, args []string) []string {
 	last := args[len(args)-1]
 	var completions []string
 	currentPrefix := strings.Join(args, " ") + " "
-	// if there is a completed criteria then suggest all again or an option
+	// if there is a completed criteria or option then suggest all again
 	for _, criteria := range append(supportedCriteria, "-r") {
 		if criteria == last {
 			for _, criteria := range supportedCriteria {
@@ -54,11 +60,8 @@ func (Sort) Complete(aerc *widgets.Aerc, args []string) []string {
 		return []string{currentPrefix + "-r"}
 	}
 	// the last item is not complete
-	for _, criteria := range supportedCriteria {
-		if strings.HasPrefix(criteria, last) {
-			completions = append(completions, currentPrefix+criteria)
-		}
-	}
+	completions = commands.FilterList(supportedCriteria, last, currentPrefix,
+		acct.UiConfig().FuzzyComplete)
 	return completions
 }
 
diff --git a/commands/commands.go b/commands/commands.go
index 70a77b92..c23df7e3 100644
--- a/commands/commands.go
+++ b/commands/commands.go
@@ -2,7 +2,6 @@ package commands
 
 import (
 	"errors"
-	"fmt"
 	"sort"
 	"strings"
 	"unicode"
@@ -74,12 +73,14 @@ func (cmds *Commands) GetCompletions(aerc *widgets.Aerc, cmd string) []string {
 		return nil
 	}
 
+	// nothing entered, list all commands
 	if len(args) == 0 {
 		names := cmds.Names()
 		sort.Strings(names)
 		return names
 	}
 
+	// complete options
 	if len(args) > 1 || cmd[len(cmd)-1] == ' ' {
 		if cmd, ok := cmds.dict()[args[0]]; ok {
 			var completions []string
@@ -101,13 +102,9 @@ func (cmds *Commands) GetCompletions(aerc *widgets.Aerc, cmd string) []string {
 		return nil
 	}
 
+	// complete available commands
 	names := cmds.Names()
-	options := make([]string, 0)
-	for _, name := range names {
-		if strings.HasPrefix(name, args[0]) {
-			options = append(options, name)
-		}
-	}
+	options := FilterList(names, args[0], "", aerc.SelectedAccount().UiConfig().FuzzyComplete)
 
 	if len(options) > 0 {
 		return options
@@ -116,35 +113,23 @@ func (cmds *Commands) GetCompletions(aerc *widgets.Aerc, cmd string) []string {
 }
 
 func GetFolders(aerc *widgets.Aerc, args []string) []string {
-	out := make([]string, 0)
 	acct := aerc.SelectedAccount()
 	if acct == nil {
-		return out
+		return make([]string, 0)
 	}
 	if len(args) == 0 {
 		return acct.Directories().List()
 	}
-	for _, dir := range acct.Directories().List() {
-		if foundInString(dir, args[0], acct.UiConfig().FuzzyFolderComplete) {
-			out = append(out, dir)
-		}
-	}
-	return out
+	return FilterList(acct.Directories().List(), args[0], "", acct.UiConfig().FuzzyComplete)
 }
 
 // CompletionFromList provides a convenience wrapper for commands to use in the
 // Complete function. It simply matches the items provided in valid
-func CompletionFromList(valid []string, args []string) []string {
-	out := make([]string, 0)
+func CompletionFromList(aerc *widgets.Aerc, valid []string, args []string) []string {
 	if len(args) == 0 {
 		return valid
 	}
-	for _, v := range valid {
-		if hasCaseSmartPrefix(v, args[0]) {
-			out = append(out, v)
-		}
-	}
-	return out
+	return FilterList(valid, args[0], "", aerc.SelectedAccount().UiConfig().FuzzyComplete)
 }
 
 func GetLabels(aerc *widgets.Aerc, args []string) []string {
@@ -172,27 +157,14 @@ func GetLabels(aerc *widgets.Aerc, args []string) []string {
 	}
 	trimmed := strings.TrimLeft(last, "+-")
 
-	out := make([]string, 0)
-	for _, label := range acct.Labels() {
-		if hasCaseSmartPrefix(label, trimmed) {
-			var prev string
-			if len(others) > 0 {
-				prev = others + " "
-			}
-			out = append(out, fmt.Sprintf("%v%v%v", prev, prefix, label))
-		}
+	var prev string
+	if len(others) > 0 {
+		prev = others + " "
 	}
+	out := FilterList(acct.Labels(), trimmed, prev+prefix, acct.UiConfig().FuzzyComplete)
 	return out
 }
 
-func foundInString(s, substring string, fuzzy bool) bool {
-	if fuzzy {
-		return caseInsensitiveContains(s, substring)
-	} else {
-		return hasCaseSmartPrefix(s, substring)
-	}
-}
-
 // hasCaseSmartPrefix checks whether s starts with prefix, using a case
 // sensitive match if and only if prefix contains upper case letters.
 func hasCaseSmartPrefix(s, prefix string) bool {
@@ -202,11 +174,6 @@ func hasCaseSmartPrefix(s, prefix string) bool {
 	return strings.HasPrefix(strings.ToLower(s), strings.ToLower(prefix))
 }
 
-func caseInsensitiveContains(s, substr string) bool {
-	s, substr = strings.ToUpper(s), strings.ToUpper(substr)
-	return strings.Contains(s, substr)
-}
-
 func hasUpper(s string) bool {
 	for _, r := range s {
 		if unicode.IsUpper(r) {
diff --git a/commands/compose/header.go b/commands/compose/header.go
index 5780aa8b..949698e5 100644
--- a/commands/compose/header.go
+++ b/commands/compose/header.go
@@ -32,7 +32,7 @@ func (Header) Aliases() []string {
 }
 
 func (Header) Complete(aerc *widgets.Aerc, args []string) []string {
-	return commands.CompletionFromList(headers, args)
+	return commands.CompletionFromList(aerc, headers, args)
 }
 
 func (Header) Execute(aerc *widgets.Aerc, args []string) error {
diff --git a/commands/ct.go b/commands/ct.go
index 7764cab8..f5f2cca9 100644
--- a/commands/ct.go
+++ b/commands/ct.go
@@ -20,17 +20,16 @@ func (ChangeTab) Aliases() []string {
 }
 
 func (ChangeTab) Complete(aerc *widgets.Aerc, args []string) []string {
+	acct := aerc.SelectedAccount()
+	if acct == nil {
+		return make([]string, 0)
+	}
+
 	if len(args) == 0 {
 		return aerc.TabNames()
 	}
 	joinedArgs := strings.Join(args, " ")
-	out := make([]string, 0)
-	for _, tab := range aerc.TabNames() {
-		if strings.HasPrefix(tab, joinedArgs) {
-			out = append(out, tab)
-		}
-	}
-	return out
+	return FilterList(aerc.TabNames(), joinedArgs, "", acct.UiConfig().FuzzyComplete)
 }
 
 func (ChangeTab) Execute(aerc *widgets.Aerc, args []string) error {
diff --git a/commands/msg/archive.go b/commands/msg/archive.go
index e73e42cf..8f832e58 100644
--- a/commands/msg/archive.go
+++ b/commands/msg/archive.go
@@ -31,7 +31,7 @@ func (Archive) Aliases() []string {
 
 func (Archive) Complete(aerc *widgets.Aerc, args []string) []string {
 	valid := []string{"flat", "year", "month"}
-	return commands.CompletionFromList(valid, args)
+	return commands.CompletionFromList(aerc, valid, args)
 }
 
 func (Archive) Execute(aerc *widgets.Aerc, args []string) error {
diff --git a/commands/util.go b/commands/util.go
index f3f9bc83..92b851a4 100644
--- a/commands/util.go
+++ b/commands/util.go
@@ -10,6 +10,8 @@ import (
 	"strings"
 	"time"
 
+	"github.com/lithammer/fuzzysearch/fuzzy"
+
 	"git.sr.ht/~rjarry/aerc/lib"
 	"git.sr.ht/~rjarry/aerc/models"
 	"git.sr.ht/~rjarry/aerc/widgets"
@@ -194,3 +196,21 @@ func MsgInfoFromUids(store *lib.MessageStore, uids []uint32) ([]*models.MessageI
 	}
 	return infos, nil
 }
+
+// FilterList takes a list of valid completions and filters it, either
+// by case smart prefix, or by fuzzy matching, prepending "prefix" to each completion
+func FilterList(valid []string, search, prefix string, isFuzzy bool) []string {
+	out := make([]string, 0)
+	if isFuzzy {
+		for _, v := range fuzzy.RankFindFold(search, valid) {
+			out = append(out, prefix+v.Target)
+		}
+	} else {
+		for _, v := range valid {
+			if hasCaseSmartPrefix(v, search) {
+				out = append(out, prefix+v)
+			}
+		}
+	}
+	return out
+}
diff --git a/config/aerc.conf b/config/aerc.conf
index a7628e39..fbbf5877 100644
--- a/config/aerc.conf
+++ b/config/aerc.conf
@@ -124,9 +124,10 @@ stylesets-dirs=
 # Default: default
 styleset-name=default
 
-# Activates fuzzy search for IMAP folders: the typed string is search in the
-#   folder tree in any position, not necessarily at the beginning.
-#fuzzy-folder-complete=false
+# Activates fuzzy search in commands and their arguments: the typed string is
+#   searched in the command or option in any position, and need not be
+#   consecutive characters in the command or option.
+#fuzzy-complete=false
 
 #[ui:account=foo]
 #
diff --git a/config/config.go b/config/config.go
index 3fecb360..8a01f503 100644
--- a/config/config.go
+++ b/config/config.go
@@ -44,7 +44,7 @@ type UIConfig struct {
 	EmptyDirlist        string        `ini:"empty-dirlist"`
 	MouseEnabled        bool          `ini:"mouse-enabled"`
 	ThreadingEnabled    bool          `ini:"threading-enabled"`
-	FuzzyFolderComplete bool          `ini:"fuzzy-folder-complete"`
+	FuzzyComplete       bool          `ini:"fuzzy-complete"`
 	NewMessageBell      bool          `ini:"new-message-bell"`
 	Spinner             string        `ini:"spinner"`
 	SpinnerDelimiter    string        `ini:"spinner-delimiter"`
@@ -622,7 +622,7 @@ func LoadConfigFromFile(root *string, logger *log.Logger) (*AercConfig, error) {
 			EmptyDirlist:        "(no folders)",
 			MouseEnabled:        false,
 			NewMessageBell:      true,
-			FuzzyFolderComplete: false,
+			FuzzyComplete:       false,
 			Spinner:             "[..]    , [..]   ,  [..]  ,   [..] ,    [..],   [..] ,  [..]  , [..]   ",
 			SpinnerDelimiter:    ",",
 			DirListFormat:       "%n %>r",
diff --git a/doc/aerc-config.5.scd b/doc/aerc-config.5.scd
index 9e8451ff..e172328a 100644
--- a/doc/aerc-config.5.scd
+++ b/doc/aerc-config.5.scd
@@ -236,11 +236,11 @@ These options are configured in the *[ui]* section of aerc.conf.
 
 	Have a look at *aerc-stylesets*(7) as to how a styleset looks like.
 
-*fuzzy-folder-complete*
-	When finding a folder with cf or move, for example, the popover will
-	how not only the folders /starting/ with the string input by the user,
-	but it will show coincidences of folders /containing/ the string in any
-	position of their name. This is case-independent.
+*fuzzy-complete*
+	When typing a command or option, the popover will now show not only the
+	items /starting/ with the string input by the user, but it will also show
+	instances of items /containing/ the string, starting at any position and
+	need not be consecutive characters in the command or option.
 
 *threading-enabled*
 	Enable a threaded viewing of messages, works with IMAP (when there's
diff --git a/go.mod b/go.mod
index 4be2d836..fac7bb39 100644
--- a/go.mod
+++ b/go.mod
@@ -23,6 +23,7 @@ require (
 	github.com/google/shlex v0.0.0-20191202100458-e7afc7fbc510
 	github.com/imdario/mergo v0.3.12
 	github.com/kyoh86/xdg v1.2.0
+	github.com/lithammer/fuzzysearch v1.1.3
 	github.com/lucasb-eyer/go-colorful v1.2.0 // indirect
 	github.com/mattn/go-isatty v0.0.14
 	github.com/mattn/go-pointer v0.0.1 // indirect
diff --git a/go.sum b/go.sum
index b828719f..48315d1c 100644
--- a/go.sum
+++ b/go.sum
@@ -168,6 +168,8 @@ github.com/kr/text v0.1.0 h1:45sCR5RtlFHMR4UwH9sdQ5TC8v0qDQCHnXt+kaKSTVE=
 github.com/kr/text v0.1.0/go.mod h1:4Jbv+DJW3UT/LiOwJeYQe1efqtUx/iVham/4vfdArNI=
 github.com/kyoh86/xdg v1.2.0 h1:CERuT/ShdTDj+A2UaX3hQ3mOV369+Sj+wyn2nIRIIkI=
 github.com/kyoh86/xdg v1.2.0/go.mod h1:/mg8zwu1+qe76oTFUBnyS7rJzk7LLC0VGEzJyJ19DHs=
+github.com/lithammer/fuzzysearch v1.1.3 h1:+t5SevHLfi3IHcTx7LT3S+od4OcUmjzxD1xmnvtgG38=
+github.com/lithammer/fuzzysearch v1.1.3/go.mod h1:1R1LRNk7yKid1BaQkmuLQaHruxcC4HmAH30Dh61Ih1Q=
 github.com/lucasb-eyer/go-colorful v1.0.3/go.mod h1:R4dSotOR9KMtayYi1e77YzuveK+i7ruzyGqttikkLy0=
 github.com/lucasb-eyer/go-colorful v1.2.0 h1:1nnpGOrhyZZuNyfu1QjKiUICQ74+3FNCN69Aj6K7nkY=
 github.com/lucasb-eyer/go-colorful v1.2.0/go.mod h1:R4dSotOR9KMtayYi1e77YzuveK+i7ruzyGqttikkLy0=