Revise ranking algorithm

1 files changed, 39 insertions, 22 deletions

diff --git a/src/pattern_test.go b/src/pattern_test.go
index 43bc5e0a..a3aa5969 100644
--- a/src/pattern_test.go
+++ b/src/pattern_test.go
@@ -8,6 +8,12 @@ import (
 	"github.com/junegunn/fzf/src/util"
 )
 
+var slab *util.Slab
+
+func init() {
+	slab = util.MakeSlab(slab16Size, slab32Size)
+}
+
 func TestParseTermsExtended(t *testing.T) {
 	terms := parseTerms(true, CaseSmart,
 		"| aaa 'bbb ^ccc ddd$ !eee !'fff !^ggg !hhh$ | ^iii$ ^xxx | 'yyy | | zzz$ | !ZZZ |")
@@ -69,26 +75,32 @@ func TestParseTermsEmpty(t *testing.T) {
 func TestExact(t *testing.T) {
 	defer clearPatternCache()
 	clearPatternCache()
-	pattern := BuildPattern(true, true, CaseSmart, true, true,
+	pattern := BuildPattern(true, algo.FuzzyMatchV2, true, CaseSmart, true, true,
 		[]Range{}, Delimiter{}, []rune("'abc"))
-	res := algo.ExactMatchNaive(
-		pattern.caseSensitive, pattern.forward, util.RunesToChars([]rune("aabbcc abc")), pattern.termSets[0][0].text)
+	res, pos := algo.ExactMatchNaive(
+		pattern.caseSensitive, pattern.forward, util.RunesToChars([]rune("aabbcc abc")), pattern.termSets[0][0].text, true, nil)
 	if res.Start != 7 || res.End != 10 {
 		t.Errorf("%s / %d / %d", pattern.termSets, res.Start, res.End)
 	}
+	if pos != nil {
+		t.Errorf("pos is expected to be nil")
+	}
 }
 
 func TestEqual(t *testing.T) {
 	defer clearPatternCache()
 	clearPatternCache()
-	pattern := BuildPattern(true, true, CaseSmart, true, true, []Range{}, Delimiter{}, []rune("^AbC$"))
+	pattern := BuildPattern(true, algo.FuzzyMatchV2, true, CaseSmart, true, true, []Range{}, Delimiter{}, []rune("^AbC$"))
 
 	match := func(str string, sidxExpected int, eidxExpected int) {
-		res := algo.EqualMatch(
-			pattern.caseSensitive, pattern.forward, util.RunesToChars([]rune(str)), pattern.termSets[0][0].text)
+		res, pos := algo.EqualMatch(
+			pattern.caseSensitive, pattern.forward, util.RunesToChars([]rune(str)), pattern.termSets[0][0].text, true, nil)
 		if res.Start != sidxExpected || res.End != eidxExpected {
 			t.Errorf("%s / %d / %d", pattern.termSets, res.Start, res.End)
 		}
+		if pos != nil {
+			t.Errorf("pos is expected to be nil")
+		}
 	}
 	match("ABC", -1, -1)
 	match("AbC", 0, 3)
@@ -97,17 +109,17 @@ func TestEqual(t *testing.T) {
 func TestCaseSensitivity(t *testing.T) {
 	defer clearPatternCache()
 	clearPatternCache()
-	pat1 := BuildPattern(true, false, CaseSmart, true, true, []Range{}, Delimiter{}, []rune("abc"))
+	pat1 := BuildPattern(true, algo.FuzzyMatchV2, false, CaseSmart, true, true, []Range{}, Delimiter{}, []rune("abc"))
 	clearPatternCache()
-	pat2 := BuildPattern(true, false, CaseSmart, true, true, []Range{}, Delimiter{}, []rune("Abc"))
+	pat2 := BuildPattern(true, algo.FuzzyMatchV2, false, CaseSmart, true, true, []Range{}, Delimiter{}, []rune("Abc"))
 	clearPatternCache()
-	pat3 := BuildPattern(true, false, CaseIgnore, true, true, []Range{}, Delimiter{}, []rune("abc"))
+	pat3 := BuildPattern(true, algo.FuzzyMatchV2, false, CaseIgnore, true, true, []Range{}, Delimiter{}, []rune("abc"))
 	clearPatternCache()
-	pat4 := BuildPattern(true, false, CaseIgnore, true, true, []Range{}, Delimiter{}, []rune("Abc"))
+	pat4 := BuildPattern(true, algo.FuzzyMatchV2, false, CaseIgnore, true, true, []Range{}, Delimiter{}, []rune("Abc"))
 	clearPatternCache()
-	pat5 := BuildPattern(true, false, CaseRespect, true, true, []Range{}, Delimiter{}, []rune("abc"))
+	pat5 := BuildPattern(true, algo.FuzzyMatchV2, false, CaseRespect, true, true, []Range{}, Delimiter{}, []rune("abc"))
 	clearPatternCache()
-	pat6 := BuildPattern(true, false, CaseRespect, true, true, []Range{}, Delimiter{}, []rune("Abc"))
+	pat6 := BuildPattern(true, algo.FuzzyMatchV2, false, CaseRespect, true, true, []Range{}, Delimiter{}, []rune("Abc"))
 
 	if string(pat1.text) != "abc" || pat1.caseSensitive != false ||
 		string(pat2.text) != "Abc" || pat2.caseSensitive != true ||
@@ -120,7 +132,7 @@ func TestCaseSensitivity(t *testing.T) {
 }
 
 func TestOrigTextAndTransformed(t *testing.T) {
-	pattern := BuildPattern(true, true, CaseSmart, true, true, []Range{}, Delimiter{}, []rune("jg"))
+	pattern := BuildPattern(true, algo.FuzzyMatchV2, true, CaseSmart, true, true, []Range{}, Delimiter{}, []rune("jg"))
 	tokens := Tokenize(util.RunesToChars([]rune("junegunn")), Delimiter{})
 	trans := Transform(tokens, []Range{Range{1, 1}})
 
@@ -133,24 +145,29 @@ func TestOrigTextAndTransformed(t *testing.T) {
 				transformed: trans},
 		}
 		pattern.extended = extended
-		matches := pattern.matchChunk(&chunk, nil) // No cache
-		if matches[0].item.text.ToString() != "junegunn" || string(*matches[0].item.origText) != "junegunn.choi" ||
-			!reflect.DeepEqual(matches[0].item.transformed, trans) {
+		matches := pattern.matchChunk(&chunk, nil, slab) // No cache
+		if !(matches[0].item.text.ToString() == "junegunn" &&
+			string(*matches[0].item.origText) == "junegunn.choi" &&
+			reflect.DeepEqual(matches[0].item.transformed, trans)) {
 			t.Error("Invalid match result", matches)
 		}
 
-		match, offsets := pattern.MatchItem(chunk[0])
-		if match.item.text.ToString() != "junegunn" || string(*match.item.origText) != "junegunn.choi" ||
-			offsets[0][0] != 0 || offsets[0][1] != 5 ||
-			!reflect.DeepEqual(match.item.transformed, trans) {
-			t.Error("Invalid match result", match)
+		match, offsets, pos := pattern.MatchItem(chunk[0], true, slab)
+		if !(match.item.text.ToString() == "junegunn" &&
+			string(*match.item.origText) == "junegunn.choi" &&
+			offsets[0][0] == 0 && offsets[0][1] == 5 &&
+			reflect.DeepEqual(match.item.transformed, trans)) {
+			t.Error("Invalid match result", match, offsets, extended)
+		}
+		if !((*pos)[0] == 4 && (*pos)[1] == 0) {
+			t.Error("Invalid pos array", *pos)
 		}
 	}
 }
 
 func TestCacheKey(t *testing.T) {
 	test := func(extended bool, patStr string, expected string, cacheable bool) {
-		pat := BuildPattern(true, extended, CaseSmart, true, true, []Range{}, Delimiter{}, []rune(patStr))
+		pat := BuildPattern(true, algo.FuzzyMatchV2, extended, CaseSmart, true, true, []Range{}, Delimiter{}, []rune(patStr))
 		if pat.CacheKey() != expected {
 			t.Errorf("Expected: %s, actual: %s", expected, pat.CacheKey())
 		}