summaryrefslogtreecommitdiff
path: root/src/algo
diff options
context:
space:
mode:
Diffstat (limited to 'src/algo')
-rw-r--r--src/algo/algo.go136
-rw-r--r--src/algo/algo_test.go73
2 files changed, 158 insertions, 51 deletions
diff --git a/src/algo/algo.go b/src/algo/algo.go
index ac7bd8b2..8656c684 100644
--- a/src/algo/algo.go
+++ b/src/algo/algo.go
@@ -22,10 +22,30 @@ func runeAt(runes []rune, index int, max int, forward bool) rune {
return runes[max-index-1]
}
+// Result conatins the results of running a match function.
+type Result struct {
+ Start int32
+ End int32
+
+ // Items are basically sorted by the lengths of matched substrings.
+ // But we slightly adjust the score with bonus for better results.
+ Bonus int32
+}
+
+type charClass int
+
+const (
+ charNonWord charClass = iota
+ charLower
+ charUpper
+ charLetter
+ charNumber
+)
+
// FuzzyMatch performs fuzzy-match
-func FuzzyMatch(caseSensitive bool, forward bool, runes []rune, pattern []rune) (int, int) {
+func FuzzyMatch(caseSensitive bool, forward bool, runes []rune, pattern []rune) Result {
if len(pattern) == 0 {
- return 0, 0
+ return Result{0, 0, 0}
}
// 0. (FIXME) How to find the shortest match?
@@ -90,12 +110,76 @@ func FuzzyMatch(caseSensitive bool, forward bool, runes []rune, pattern []rune)
}
}
}
- if forward {
- return sidx, eidx
+
+ // Calculate the bonus. This can't be done at the same time as the
+ // pattern scan above because 'forward' may be false.
+ if !forward {
+ sidx, eidx = lenRunes-eidx, lenRunes-sidx
+ }
+
+ var bonus int32
+ pidx := 0
+ consecutive := false
+ prevClass := charNonWord
+ for index := 0; index < eidx; index++ {
+ char := runes[index]
+ var class charClass
+ if unicode.IsLower(char) {
+ class = charLower
+ } else if unicode.IsUpper(char) {
+ class = charUpper
+ } else if unicode.IsLetter(char) {
+ class = charLetter
+ } else if unicode.IsNumber(char) {
+ class = charNumber
+ } else {
+ class = charNonWord
+ }
+
+ var point int32
+ if prevClass == charNonWord && class != charNonWord {
+ // Word boundary
+ point = 2
+ } else if prevClass == charLower && class == charUpper ||
+ prevClass != charNumber && class == charNumber {
+ // camelCase letter123
+ point = 1
+ }
+ prevClass = class
+
+ if index >= sidx {
+ if !caseSensitive {
+ if char >= 'A' && char <= 'Z' {
+ char += 32
+ } else if char > unicode.MaxASCII {
+ char = unicode.To(unicode.LowerCase, char)
+ }
+ }
+ pchar := pattern[pidx]
+ if pchar == char {
+ // Boost bonus for the first character in the pattern
+ if pidx == 0 {
+ point *= 2
+ }
+ // Bonus to consecutive matching chars
+ if consecutive {
+ point++
+ }
+ bonus += point
+
+ if pidx++; pidx == lenPattern {
+ break
+ }
+ consecutive = true
+ } else {
+ consecutive = false
+ }
+ }
}
- return lenRunes - eidx, lenRunes - sidx
+
+ return Result{int32(sidx), int32(eidx), bonus}
}
- return -1, -1
+ return Result{-1, -1, 0}
}
// ExactMatchNaive is a basic string searching algorithm that handles case
@@ -105,16 +189,17 @@ func FuzzyMatch(caseSensitive bool, forward bool, runes []rune, pattern []rune)
//
// We might try to implement better algorithms in the future:
// http://en.wikipedia.org/wiki/String_searching_algorithm
-func ExactMatchNaive(caseSensitive bool, forward bool, runes []rune, pattern []rune) (int, int) {
+func ExactMatchNaive(caseSensitive bool, forward bool, runes []rune, pattern []rune) Result {
+ // Note: ExactMatchNaive always return a zero bonus.
if len(pattern) == 0 {
- return 0, 0
+ return Result{0, 0, 0}
}
lenRunes := len(runes)
lenPattern := len(pattern)
if lenRunes < lenPattern {
- return -1, -1
+ return Result{-1, -1, 0}
}
pidx := 0
@@ -132,22 +217,23 @@ func ExactMatchNaive(caseSensitive bool, forward bool, runes []rune, pattern []r
pidx++
if pidx == lenPattern {
if forward {
- return index - lenPattern + 1, index + 1
+ return Result{int32(index - lenPattern + 1), int32(index + 1), 0}
}
- return lenRunes - (index + 1), lenRunes - (index - lenPattern + 1)
+ return Result{int32(lenRunes - (index + 1)), int32(lenRunes - (index - lenPattern + 1)), 0}
}
} else {
index -= pidx
pidx = 0
}
}
- return -1, -1
+ return Result{-1, -1, 0}
}
// PrefixMatch performs prefix-match
-func PrefixMatch(caseSensitive bool, forward bool, runes []rune, pattern []rune) (int, int) {
+func PrefixMatch(caseSensitive bool, forward bool, runes []rune, pattern []rune) Result {
+ // Note: PrefixMatch always return a zero bonus.
if len(runes) < len(pattern) {
- return -1, -1
+ return Result{-1, -1, 0}
}
for index, r := range pattern {
@@ -156,19 +242,20 @@ func PrefixMatch(caseSensitive bool, forward bool, runes []rune, pattern []rune)
char = unicode.ToLower(char)
}
if char != r {
- return -1, -1
+ return Result{-1, -1, 0}
}
}
- return 0, len(pattern)
+ return Result{0, int32(len(pattern)), 0}
}
// SuffixMatch performs suffix-match
-func SuffixMatch(caseSensitive bool, forward bool, input []rune, pattern []rune) (int, int) {
+func SuffixMatch(caseSensitive bool, forward bool, input []rune, pattern []rune) Result {
+ // Note: SuffixMatch always return a zero bonus.
runes := util.TrimRight(input)
trimmedLen := len(runes)
diff := trimmedLen - len(pattern)
if diff < 0 {
- return -1, -1
+ return Result{-1, -1, 0}
}
for index, r := range pattern {
@@ -177,23 +264,24 @@ func SuffixMatch(caseSensitive bool, forward bool, input []rune, pattern []rune)
char = unicode.ToLower(char)
}
if char != r {
- return -1, -1
+ return Result{-1, -1, 0}
}
}
- return trimmedLen - len(pattern), trimmedLen
+ return Result{int32(trimmedLen - len(pattern)), int32(trimmedLen), 0}
}
// EqualMatch performs equal-match
-func EqualMatch(caseSensitive bool, forward bool, runes []rune, pattern []rune) (int, int) {
+func EqualMatch(caseSensitive bool, forward bool, runes []rune, pattern []rune) Result {
+ // Note: EqualMatch always return a zero bonus.
if len(runes) != len(pattern) {
- return -1, -1
+ return Result{-1, -1, 0}
}
runesStr := string(runes)
if !caseSensitive {
runesStr = strings.ToLower(runesStr)
}
if runesStr == string(pattern) {
- return 0, len(pattern)
+ return Result{0, int32(len(pattern)), 0}
}
- return -1, -1
+ return Result{-1, -1, 0}
}
diff --git a/src/algo/algo_test.go b/src/algo/algo_test.go
index 06ec5eae..a124d050 100644
--- a/src/algo/algo_test.go
+++ b/src/algo/algo_test.go
@@ -5,65 +5,84 @@ import (
"testing"
)
-func assertMatch(t *testing.T, fun func(bool, bool, []rune, []rune) (int, int), caseSensitive bool, forward bool, input string, pattern string, sidx int, eidx int) {
+func assertMatch(t *testing.T, fun func(bool, bool, []rune, []rune) Result, caseSensitive, forward bool, input, pattern string, sidx int32, eidx int32, bonus int32) {
if !caseSensitive {
pattern = strings.ToLower(pattern)
}
- s, e := fun(caseSensitive, forward, []rune(input), []rune(pattern))
- if s != sidx {
- t.Errorf("Invalid start index: %d (expected: %d, %s / %s)", s, sidx, input, pattern)
+ res := fun(caseSensitive, forward, []rune(input), []rune(pattern))
+ if res.Start != sidx {
+ t.Errorf("Invalid start index: %d (expected: %d, %s / %s)", res.Start, sidx, input, pattern)
}
- if e != eidx {
- t.Errorf("Invalid end index: %d (expected: %d, %s / %s)", e, eidx, input, pattern)
+ if res.End != eidx {
+ t.Errorf("Invalid end index: %d (expected: %d, %s / %s)", res.End, eidx, input, pattern)
+ }
+ if res.Bonus != bonus {
+ t.Errorf("Invalid bonus: %d (expected: %d, %s / %s)", res.Bonus, bonus, input, pattern)
}
}
func TestFuzzyMatch(t *testing.T) {
- assertMatch(t, FuzzyMatch, false, true, "fooBarbaz", "oBZ", 2, 9)
- assertMatch(t, FuzzyMatch, true, true, "fooBarbaz", "oBZ", -1, -1)
- assertMatch(t, FuzzyMatch, true, true, "fooBarbaz", "oBz", 2, 9)
- assertMatch(t, FuzzyMatch, true, true, "fooBarbaz", "fooBarbazz", -1, -1)
+ assertMatch(t, FuzzyMatch, false, true, "fooBarbaz", "oBZ", 2, 9, 2)
+ assertMatch(t, FuzzyMatch, false, true, "foo bar baz", "fbb", 0, 9, 8)
+ assertMatch(t, FuzzyMatch, false, true, "/AutomatorDocument.icns", "rdoc", 9, 13, 4)
+ assertMatch(t, FuzzyMatch, false, true, "/man1/zshcompctl.1", "zshc", 6, 10, 7)
+ assertMatch(t, FuzzyMatch, false, true, "/.oh-my-zsh/cache", "zshc", 8, 13, 8)
+ assertMatch(t, FuzzyMatch, false, true, "ab0123 456", "12356", 3, 10, 3)
+ assertMatch(t, FuzzyMatch, false, true, "abc123 456", "12356", 3, 10, 5)
+
+ assertMatch(t, FuzzyMatch, false, true, "foo/bar/baz", "fbb", 0, 9, 8)
+ assertMatch(t, FuzzyMatch, false, true, "fooBarBaz", "fbb", 0, 7, 6)
+ assertMatch(t, FuzzyMatch, false, true, "foo barbaz", "fbb", 0, 8, 6)
+ assertMatch(t, FuzzyMatch, false, true, "fooBar Baz", "foob", 0, 4, 8)
+ assertMatch(t, FuzzyMatch, true, true, "fooBarbaz", "oBZ", -1, -1, 0)
+ assertMatch(t, FuzzyMatch, true, true, "fooBarbaz", "oBz", 2, 9, 2)
+ assertMatch(t, FuzzyMatch, true, true, "Foo Bar Baz", "fbb", -1, -1, 0)
+ assertMatch(t, FuzzyMatch, true, true, "Foo/Bar/Baz", "FBB", 0, 9, 8)
+ assertMatch(t, FuzzyMatch, true, true, "FooBarBaz", "FBB", 0, 7, 6)
+ assertMatch(t, FuzzyMatch, true, true, "foo BarBaz", "fBB", 0, 8, 7)
+ assertMatch(t, FuzzyMatch, true, true, "FooBar Baz", "FooB", 0, 4, 8)
+ assertMatch(t, FuzzyMatch, true, true, "fooBarbaz", "fooBarbazz", -1, -1, 0)
}
func TestFuzzyMatchBackward(t *testing.T) {
- assertMatch(t, FuzzyMatch, false, true, "foobar fb", "fb", 0, 4)
- assertMatch(t, FuzzyMatch, false, false, "foobar fb", "fb", 7, 9)
+ assertMatch(t, FuzzyMatch, false, true, "foobar fb", "fb", 0, 4, 4)
+ assertMatch(t, FuzzyMatch, false, false, "foobar fb", "fb", 7, 9, 5)
}
func TestExactMatchNaive(t *testing.T) {
for _, dir := range []bool{true, false} {
- assertMatch(t, ExactMatchNaive, false, dir, "fooBarbaz", "oBA", 2, 5)
- assertMatch(t, ExactMatchNaive, true, dir, "fooBarbaz", "oBA", -1, -1)
- assertMatch(t, ExactMatchNaive, true, dir, "fooBarbaz", "fooBarbazz", -1, -1)
+ assertMatch(t, ExactMatchNaive, false, dir, "fooBarbaz", "oBA", 2, 5, 0)
+ assertMatch(t, ExactMatchNaive, true, dir, "fooBarbaz", "oBA", -1, -1, 0)
+ assertMatch(t, ExactMatchNaive, true, dir, "fooBarbaz", "fooBarbazz", -1, -1, 0)
}
}
func TestExactMatchNaiveBackward(t *testing.T) {
- assertMatch(t, ExactMatchNaive, false, true, "foobar foob", "oo", 1, 3)
- assertMatch(t, ExactMatchNaive, false, false, "foobar foob", "oo", 8, 10)
+ assertMatch(t, ExactMatchNaive, false, true, "foobar foob", "oo", 1, 3, 0)
+ assertMatch(t, ExactMatchNaive, false, false, "foobar foob", "oo", 8, 10, 0)
}
func TestPrefixMatch(t *testing.T) {
for _, dir := range []bool{true, false} {
- assertMatch(t, PrefixMatch, false, dir, "fooBarbaz", "Foo", 0, 3)
- assertMatch(t, PrefixMatch, true, dir, "fooBarbaz", "Foo", -1, -1)
- assertMatch(t, PrefixMatch, false, dir, "fooBarbaz", "baz", -1, -1)
+ assertMatch(t, PrefixMatch, false, dir, "fooBarbaz", "Foo", 0, 3, 0)
+ assertMatch(t, PrefixMatch, true, dir, "fooBarbaz", "Foo", -1, -1, 0)
+ assertMatch(t, PrefixMatch, false, dir, "fooBarbaz", "baz", -1, -1, 0)
}
}
func TestSuffixMatch(t *testing.T) {
for _, dir := range []bool{true, false} {
- assertMatch(t, SuffixMatch, false, dir, "fooBarbaz", "Foo", -1, -1)
- assertMatch(t, SuffixMatch, false, dir, "fooBarbaz", "baz", 6, 9)
- assertMatch(t, SuffixMatch, true, dir, "fooBarbaz", "Baz", -1, -1)
+ assertMatch(t, SuffixMatch, false, dir, "fooBarbaz", "Foo", -1, -1, 0)
+ assertMatch(t, SuffixMatch, false, dir, "fooBarbaz", "baz", 6, 9, 0)
+ assertMatch(t, SuffixMatch, true, dir, "fooBarbaz", "Baz", -1, -1, 0)
}
}
func TestEmptyPattern(t *testing.T) {
for _, dir := range []bool{true, false} {
- assertMatch(t, FuzzyMatch, true, dir, "foobar", "", 0, 0)
- assertMatch(t, ExactMatchNaive, true, dir, "foobar", "", 0, 0)
- assertMatch(t, PrefixMatch, true, dir, "foobar", "", 0, 0)
- assertMatch(t, SuffixMatch, true, dir, "foobar", "", 6, 6)
+ assertMatch(t, FuzzyMatch, true, dir, "foobar", "", 0, 0, 0)
+ assertMatch(t, ExactMatchNaive, true, dir, "foobar", "", 0, 0, 0)
+ assertMatch(t, PrefixMatch, true, dir, "foobar", "", 0, 0, 0)
+ assertMatch(t, SuffixMatch, true, dir, "foobar", "", 6, 6, 0)
}
}
generated by cgit v1.2.3 (git 2.25.1) at 2026-04-29 18:25:23 +0000