diff options
author | Junegunn Choi <junegunn.c@gmail.com> | 2022-08-28 22:16:57 +0900 |
---|---|---|
committer | Junegunn Choi <junegunn.c@gmail.com> | 2022-08-28 22:22:39 +0900 |
commit | 6fb41a202a97ad3f2437f6e5aee8890268560412 (patch) | |
tree | 5c4d9002481b8314b458bf6ef0812eac04cd40a7 /src/algo | |
parent | 4bef330ce15d3ae80959415c24aba4700f5cbe35 (diff) |
Add --scheme=[default|path|history] option to choose scoring scheme
Close #2909
Close #2930
Diffstat (limited to 'src/algo')
-rw-r--r-- | src/algo/algo.go | 49 | ||||
-rw-r--r-- | src/algo/algo_test.go | 38 |
2 files changed, 58 insertions, 29 deletions
diff --git a/src/algo/algo.go b/src/algo/algo.go index 15214a68..50dd466c 100644 --- a/src/algo/algo.go +++ b/src/algo/algo.go @@ -80,6 +80,7 @@ Scoring criteria import ( "bytes" "fmt" + "os" "strings" "unicode" "unicode/utf8" @@ -89,7 +90,8 @@ import ( var DEBUG bool -const delimiterChars = "/,:;|" +var delimiterChars = "/,:;|" + const whiteChars = " \t\n\v\f\r\x85\xA0" func indexAt(index int, max int, forward bool) int { @@ -120,12 +122,6 @@ const ( // in web2 dictionary and my file system. bonusBoundary = scoreMatch / 2 - // Extra bonus for word boundary after whitespace character or beginning of the string - bonusBoundaryWhite = bonusBoundary + 2 - - // Extra bonus for word boundary after slash, colon, semi-colon, and comma - bonusBoundaryDelimiter = bonusBoundary + 1 - // Although bonus point for non-word characters is non-contextual, we need it // for computing bonus points for consecutive chunks starting with a non-word // character. @@ -149,6 +145,16 @@ const ( bonusFirstCharMultiplier = 2 ) +var ( + // Extra bonus for word boundary after whitespace character or beginning of the string + bonusBoundaryWhite int16 = bonusBoundary + 2 + + // Extra bonus for word boundary after slash, colon, semi-colon, and comma + bonusBoundaryDelimiter int16 = bonusBoundary + 1 + + initialCharClass charClass = charWhite +) + type charClass int const ( @@ -161,6 +167,29 @@ const ( charNumber ) +func Init(scheme string) bool { + switch scheme { + case "default": + bonusBoundaryWhite = bonusBoundary + 2 + bonusBoundaryDelimiter = bonusBoundary + 1 + case "path": + bonusBoundaryWhite = bonusBoundary + bonusBoundaryDelimiter = bonusBoundary + 1 + if os.PathSeparator == '/' { + delimiterChars = "/" + } else { + delimiterChars = string([]rune{os.PathSeparator, '/'}) + } + initialCharClass = charDelimiter + case "history": + bonusBoundaryWhite = bonusBoundary + bonusBoundaryDelimiter = bonusBoundary + default: + return false + } + return true +} + func posArray(withPos bool, len int) *[]int { if withPos { pos := make([]int, 0, len) @@ -407,7 +436,7 @@ func FuzzyMatchV2(caseSensitive bool, normalize bool, forward bool, input *util. // Phase 2. Calculate bonus for each point maxScore, maxScorePos := int16(0), 0 pidx, lastIdx := 0, 0 - pchar0, pchar, prevH0, prevClass, inGap := pattern[0], pattern[0], int16(0), charWhite, false + pchar0, pchar, prevH0, prevClass, inGap := pattern[0], pattern[0], int16(0), initialCharClass, false Tsub := T[idx:] H0sub, C0sub, Bsub := H0[idx:][:len(Tsub)], C0[idx:][:len(Tsub)], B[idx:][:len(Tsub)] for off, char := range Tsub { @@ -910,8 +939,8 @@ func EqualMatch(caseSensitive bool, normalize bool, forward bool, text *util.Cha match = runesStr == string(pattern) } if match { - return Result{trimmedLen, trimmedLen + lenPattern, (scoreMatch+bonusBoundaryWhite)*lenPattern + - (bonusFirstCharMultiplier-1)*bonusBoundaryWhite}, nil + return Result{trimmedLen, trimmedLen + lenPattern, (scoreMatch+int(bonusBoundaryWhite))*lenPattern + + (bonusFirstCharMultiplier-1)*int(bonusBoundaryWhite)}, nil } return Result{-1, -1, 0}, nil } diff --git a/src/algo/algo_test.go b/src/algo/algo_test.go index 2dbe3833..a7c4e1d3 100644 --- a/src/algo/algo_test.go +++ b/src/algo/algo_test.go @@ -45,29 +45,29 @@ func TestFuzzyMatch(t *testing.T) { assertMatch(t, fn, false, forward, "fooBarbaz1", "oBZ", 2, 9, scoreMatch*3+bonusCamel123+scoreGapStart+scoreGapExtension*3) assertMatch(t, fn, false, forward, "foo bar baz", "fbb", 0, 9, - scoreMatch*3+bonusBoundaryWhite*bonusFirstCharMultiplier+ - bonusBoundaryWhite*2+2*scoreGapStart+4*scoreGapExtension) + scoreMatch*3+int(bonusBoundaryWhite)*bonusFirstCharMultiplier+ + int(bonusBoundaryWhite)*2+2*scoreGapStart+4*scoreGapExtension) assertMatch(t, fn, false, forward, "/AutomatorDocument.icns", "rdoc", 9, 13, scoreMatch*4+bonusCamel123+bonusConsecutive*2) assertMatch(t, fn, false, forward, "/man1/zshcompctl.1", "zshc", 6, 10, - scoreMatch*4+bonusBoundaryDelimiter*bonusFirstCharMultiplier+bonusBoundaryDelimiter*3) + scoreMatch*4+int(bonusBoundaryDelimiter)*bonusFirstCharMultiplier+int(bonusBoundaryDelimiter)*3) assertMatch(t, fn, false, forward, "/.oh-my-zsh/cache", "zshc", 8, 13, - scoreMatch*4+bonusBoundary*bonusFirstCharMultiplier+bonusBoundary*2+scoreGapStart+bonusBoundaryDelimiter) + scoreMatch*4+bonusBoundary*bonusFirstCharMultiplier+bonusBoundary*2+scoreGapStart+int(bonusBoundaryDelimiter)) assertMatch(t, fn, false, forward, "ab0123 456", "12356", 3, 10, scoreMatch*5+bonusConsecutive*3+scoreGapStart+scoreGapExtension) assertMatch(t, fn, false, forward, "abc123 456", "12356", 3, 10, scoreMatch*5+bonusCamel123*bonusFirstCharMultiplier+bonusCamel123*2+bonusConsecutive+scoreGapStart+scoreGapExtension) assertMatch(t, fn, false, forward, "foo/bar/baz", "fbb", 0, 9, - scoreMatch*3+bonusBoundaryWhite*bonusFirstCharMultiplier+ - bonusBoundaryDelimiter*2+2*scoreGapStart+4*scoreGapExtension) + scoreMatch*3+int(bonusBoundaryWhite)*bonusFirstCharMultiplier+ + int(bonusBoundaryDelimiter)*2+2*scoreGapStart+4*scoreGapExtension) assertMatch(t, fn, false, forward, "fooBarBaz", "fbb", 0, 7, - scoreMatch*3+bonusBoundaryWhite*bonusFirstCharMultiplier+ + scoreMatch*3+int(bonusBoundaryWhite)*bonusFirstCharMultiplier+ bonusCamel123*2+2*scoreGapStart+2*scoreGapExtension) assertMatch(t, fn, false, forward, "foo barbaz", "fbb", 0, 8, - scoreMatch*3+bonusBoundaryWhite*bonusFirstCharMultiplier+bonusBoundaryWhite+ + scoreMatch*3+int(bonusBoundaryWhite)*bonusFirstCharMultiplier+int(bonusBoundaryWhite)+ scoreGapStart*2+scoreGapExtension*3) assertMatch(t, fn, false, forward, "fooBar Baz", "foob", 0, 4, - scoreMatch*4+bonusBoundaryWhite*bonusFirstCharMultiplier+bonusBoundaryWhite*3) + scoreMatch*4+int(bonusBoundaryWhite)*bonusFirstCharMultiplier+int(bonusBoundaryWhite)*3) assertMatch(t, fn, false, forward, "xFoo-Bar Baz", "foo-b", 1, 6, scoreMatch*5+bonusCamel123*bonusFirstCharMultiplier+bonusCamel123*2+ bonusNonWord+bonusBoundary) @@ -75,14 +75,14 @@ func TestFuzzyMatch(t *testing.T) { assertMatch(t, fn, true, forward, "fooBarbaz", "oBz", 2, 9, scoreMatch*3+bonusCamel123+scoreGapStart+scoreGapExtension*3) assertMatch(t, fn, true, forward, "Foo/Bar/Baz", "FBB", 0, 9, - scoreMatch*3+bonusBoundaryWhite*bonusFirstCharMultiplier+bonusBoundaryDelimiter*2+ + scoreMatch*3+int(bonusBoundaryWhite)*bonusFirstCharMultiplier+int(bonusBoundaryDelimiter)*2+ scoreGapStart*2+scoreGapExtension*4) assertMatch(t, fn, true, forward, "FooBarBaz", "FBB", 0, 7, - scoreMatch*3+bonusBoundaryWhite*bonusFirstCharMultiplier+bonusCamel123*2+ + scoreMatch*3+int(bonusBoundaryWhite)*bonusFirstCharMultiplier+bonusCamel123*2+ scoreGapStart*2+scoreGapExtension*2) assertMatch(t, fn, true, forward, "FooBar Baz", "FooB", 0, 4, - scoreMatch*4+bonusBoundaryWhite*bonusFirstCharMultiplier+bonusBoundaryWhite*2+ - util.Max(bonusCamel123, bonusBoundaryWhite)) + scoreMatch*4+int(bonusBoundaryWhite)*bonusFirstCharMultiplier+int(bonusBoundaryWhite)*2+ + util.Max(bonusCamel123, int(bonusBoundaryWhite))) // Consecutive bonus updated assertMatch(t, fn, true, forward, "foo-bar", "o-ba", 2, 6, @@ -98,10 +98,10 @@ func TestFuzzyMatch(t *testing.T) { func TestFuzzyMatchBackward(t *testing.T) { assertMatch(t, FuzzyMatchV1, false, true, "foobar fb", "fb", 0, 4, - scoreMatch*2+bonusBoundaryWhite*bonusFirstCharMultiplier+ + scoreMatch*2+int(bonusBoundaryWhite)*bonusFirstCharMultiplier+ scoreGapStart+scoreGapExtension) assertMatch(t, FuzzyMatchV1, false, false, "foobar fb", "fb", 7, 9, - scoreMatch*2+bonusBoundaryWhite*bonusFirstCharMultiplier+bonusBoundaryWhite) + scoreMatch*2+int(bonusBoundaryWhite)*bonusFirstCharMultiplier+int(bonusBoundaryWhite)) } func TestExactMatchNaive(t *testing.T) { @@ -114,9 +114,9 @@ func TestExactMatchNaive(t *testing.T) { assertMatch(t, ExactMatchNaive, false, dir, "/AutomatorDocument.icns", "rdoc", 9, 13, scoreMatch*4+bonusCamel123+bonusConsecutive*2) assertMatch(t, ExactMatchNaive, false, dir, "/man1/zshcompctl.1", "zshc", 6, 10, - scoreMatch*4+bonusBoundaryDelimiter*(bonusFirstCharMultiplier+3)) + scoreMatch*4+int(bonusBoundaryDelimiter)*(bonusFirstCharMultiplier+3)) assertMatch(t, ExactMatchNaive, false, dir, "/.oh-my-zsh/cache", "zsh/c", 8, 13, - scoreMatch*5+bonusBoundary*(bonusFirstCharMultiplier+3)+bonusBoundaryDelimiter) + scoreMatch*5+bonusBoundary*(bonusFirstCharMultiplier+3)+int(bonusBoundaryDelimiter)) } } @@ -128,7 +128,7 @@ func TestExactMatchNaiveBackward(t *testing.T) { } func TestPrefixMatch(t *testing.T) { - score := scoreMatch*3 + bonusBoundaryWhite*bonusFirstCharMultiplier + bonusBoundaryWhite*2 + score := scoreMatch*3 + int(bonusBoundaryWhite)*bonusFirstCharMultiplier + int(bonusBoundaryWhite)*2 for _, dir := range []bool{true, false} { assertMatch(t, PrefixMatch, true, dir, "fooBarbaz", "Foo", -1, -1, 0) @@ -159,7 +159,7 @@ func TestSuffixMatch(t *testing.T) { // Only when the pattern doesn't end with a space assertMatch(t, SuffixMatch, false, dir, "fooBarbaz ", "baz ", 6, 10, - scoreMatch*4+bonusConsecutive*2+bonusBoundaryWhite) + scoreMatch*4+bonusConsecutive*2+int(bonusBoundaryWhite)) } } |