STRLCPY/fzf

Tweak bonus points to word boundaries

Close https://github.com/junegunn/fzf.vim/issues/1004

  # jobs/latency.js is favored over job_latency.js
  printf 'job_latency.js\njobs/latency.js' | fzf -qlatency

Junegunn Choi committed 2 years ago

c3a7a24e

1 parent bbbcd780

Total 3 files Show one by one

■ ■ ■ ■ ■ ■

CHANGELOG.md

1	1		CHANGELOG
2	2		=========
3	3
	4	+	0.32.0
	5	+	------
	6	+	- Updated the scoring algorithm
	7	+	- Different bonus points to different categories of word boundaries
	8	+	(listed higher to lower bonus point)
	9	+	- Word after whitespace characters or beginning of the string
	10	+	- Word after common delimiter characters (`/,:;\|`)
	11	+	- Word after other non-word characters
	12	+	````sh
	13	+	# foo/bar.sh` is preferred over `foo-bar.sh` on `bar`
	14	+	fzf --query bar --height 4 << EOF
	15	+	foo-bar.sh
	16	+	foo/bar.sh
	17	+	EOF
	18	+	```
	19	+	- Bug fixes and improvements
	20	+
4	21		0.31.0
5	22		------
6	23		- Added support for an alternative preview window layout that is activated
		skipped 1236 lines

■ ■ ■ ■ ■ ■

src/algo/algo.go

		skipped 88 lines
89	89
90	90		var DEBUG bool
91	91
	92	+	const delimiterChars = "/,:;\|"
	93	+	const whiteChars = " \t\n\v\f\r\x85\xA0"
	94	+
92	95		func indexAt(index int, max int, forward bool) int {
93	96		if forward {
94	97		return index
		skipped 21 lines
116	119		// 8 characters, which is approximately the average length of the words found
117	120		// in web2 dictionary and my file system.
118	121		bonusBoundary = scoreMatch / 2
	122	+
	123	+	// Extra bonus for word boundary after whitespace character or beginning of the string
	124	+	bonusBoundaryWhite = bonusBoundary + 2
	125	+
	126	+	// Extra bonus for word boundary after slash, colon, semi-colon, and comma
	127	+	bonusBoundaryDelimiter = bonusBoundary + 1
119	128
120	129		// Although bonus point for non-word characters is non-contextual, we need it
121	130		// for computing bonus points for consecutive chunks starting with a non-word
		skipped 21 lines
143	152		type charClass int
144	153
145	154		const (
146		-	charNonWord charClass = iota
	155	+	charWhite charClass = iota
	156	+	charNonWord
	157	+	charDelimiter
147	158		charLower
148	159		charUpper
149	160		charLetter
		skipped 31 lines
181	192		return charUpper
182	193		} else if char >= '0' && char <= '9' {
183	194		return charNumber
	195	+	} else if strings.IndexRune(whiteChars, char) >= 0 {
	196	+	return charWhite
	197	+	} else if strings.IndexRune(delimiterChars, char) >= 0 {
	198	+	return charDelimiter
184	199		}
185	200		return charNonWord
186	201		}
		skipped 7 lines
194	209		return charNumber
195	210		} else if unicode.IsLetter(char) {
196	211		return charLetter
	212	+	} else if unicode.IsSpace(char) {
	213	+	return charWhite
	214	+	} else if strings.IndexRune(delimiterChars, char) >= 0 {
	215	+	return charDelimiter
197	216		}
198	217		return charNonWord
199	218		}
		skipped 6 lines
206	225		}
207	226
208	227		func bonusFor(prevClass charClass, class charClass) int16 {
209		-	if prevClass == charNonWord && class != charNonWord {
210		-	// Word boundary
211		-	return bonusBoundary
212		-	} else if prevClass == charLower && class == charUpper \|\|
	228	+	if class > charNonWord {
	229	+	if prevClass == charWhite {
	230	+	// Word boundary after whitespace
	231	+	return bonusBoundaryWhite
	232	+	} else if prevClass == charDelimiter {
	233	+	// Word boundary after a delimiter character
	234	+	return bonusBoundaryDelimiter
	235	+	} else if prevClass == charNonWord {
	236	+	// Word boundary
	237	+	return bonusBoundary
	238	+	}
	239	+	}
	240	+	if prevClass == charLower && class == charUpper \|\|
213	241		prevClass != charNumber && class == charNumber {
214	242		// camelCase letter123
215	243		return bonusCamel123
216	244		} else if class == charNonWord {
217	245		return bonusNonWord
	246	+	} else if class == charWhite {
	247	+	return bonusBoundaryWhite
218	248		}
219	249		return 0
220	250		}
221	251
222	252		func bonusAt(input *util.Chars, idx int) int16 {
223	253		if idx == 0 {
224		-	return bonusBoundary
	254	+	return bonusBoundaryWhite
225	255		}
226	256		return bonusFor(charClassOf(input.Get(idx-1)), charClassOf(input.Get(idx)))
227	257		}
		skipped 149 lines
377	407		// Phase 2. Calculate bonus for each point
378	408		maxScore, maxScorePos := int16(0), 0
379	409		pidx, lastIdx := 0, 0
380		-	pchar0, pchar, prevH0, prevClass, inGap := pattern[0], pattern[0], int16(0), charNonWord, false
	410	+	pchar0, pchar, prevH0, prevClass, inGap := pattern[0], pattern[0], int16(0), charWhite, false
381	411		Tsub := T[idx:]
382	412		H0sub, C0sub, Bsub := H0[idx:][:len(Tsub)], C0[idx:][:len(Tsub)], B[idx:][:len(Tsub)]
383	413		for off, char := range Tsub {
		skipped 33 lines
417	447		C0sub[off] = 1
418	448		if M == 1 && (forward && score > maxScore \|\| !forward && score >= maxScore) {
419	449		maxScore, maxScorePos = score, idx+off
420		-	if forward && bonus == bonusBoundary {
	450	+	if forward && bonus >= bonusBoundary {
421	451		break
422	452		}
423	453		}
		skipped 62 lines
486	516		s1 = Hdiag[off] + scoreMatch
487	517		b := Bsub[off]
488	518		consecutive = Cdiag[off] + 1
489		-	// Break consecutive chunk
490		-	if b == bonusBoundary {
491		-	consecutive = 1
492		-	} else if consecutive > 1 {
493		-	b = util.Max16(b, util.Max16(bonusConsecutive, B[col-int(consecutive)+1]))
	519	+	if consecutive > 1 {
	520	+	fb := B[col-int(consecutive)+1]
	521	+	// Break consecutive chunk
	522	+	if b >= bonusBoundary && b > fb {
	523	+	consecutive = 1
	524	+	} else {
	525	+	b = util.Max16(b, util.Max16(bonusConsecutive, fb))
	526	+	}
494	527		}
495	528		if s1+b < s2 {
496	529		s1 += Bsub[off]
		skipped 58 lines
555	588		func calculateScore(caseSensitive bool, normalize bool, text util.Chars, pattern []rune, sidx int, eidx int, withPos bool) (int, []int) {
556	589		pidx, score, inGap, consecutive, firstBonus := 0, 0, false, 0, int16(0)
557	590		pos := posArray(withPos, len(pattern))
558		-	prevClass := charNonWord
	591	+	prevClass := charWhite
559	592		if sidx > 0 {
560	593		prevClass = charClassOf(text.Get(sidx - 1))
561	594		}
		skipped 21 lines
583	616		firstBonus = bonus
584	617		} else {
585	618		// Break consecutive chunk
586		-	if bonus == bonusBoundary {
	619	+	if bonus >= bonusBoundary && bonus > firstBonus {
587	620		firstBonus = bonus
588	621		}
589	622		bonus = util.Max16(util.Max16(bonus, firstBonus), bonusConsecutive)
		skipped 151 lines
741	774		if bonus > bestBonus {
742	775		bestPos, bestBonus = index, bonus
743	776		}
744		-	if bonus == bonusBoundary {
	777	+	if bonus >= bonusBoundary {
745	778		break
746	779		}
747	780		index -= pidx - 1
		skipped 129 lines
877	910		match = runesStr == string(pattern)
878	911		}
879	912		if match {
880		-	return Result{trimmedLen, trimmedLen + lenPattern, (scoreMatch+bonusBoundary)*lenPattern +
881		-	(bonusFirstCharMultiplier-1)*bonusBoundary}, nil
	913	+	return Result{trimmedLen, trimmedLen + lenPattern, (scoreMatch+bonusBoundaryWhite)*lenPattern +
	914	+	(bonusFirstCharMultiplier-1)*bonusBoundaryWhite}, nil
882	915		}
883	916		return Result{-1, -1, 0}, nil
884	917		}
		skipped 1 lines

■ ■ ■ ■ ■ ■

src/algo/algo_test.go

		skipped 44 lines
45	45		assertMatch(t, fn, false, forward, "fooBarbaz1", "oBZ", 2, 9,
46	46		scoreMatch3+bonusCamel123+scoreGapStart+scoreGapExtension3)
47	47		assertMatch(t, fn, false, forward, "foo bar baz", "fbb", 0, 9,
48		-	scoreMatch3+bonusBoundarybonusFirstCharMultiplier+
49		-	bonusBoundary2+2scoreGapStart+4*scoreGapExtension)
	48	+	scoreMatch3+bonusBoundaryWhitebonusFirstCharMultiplier+
	49	+	bonusBoundaryWhite2+2scoreGapStart+4*scoreGapExtension)
50	50		assertMatch(t, fn, false, forward, "/AutomatorDocument.icns", "rdoc", 9, 13,
51	51		scoreMatch4+bonusCamel123+bonusConsecutive2)
52	52		assertMatch(t, fn, false, forward, "/man1/zshcompctl.1", "zshc", 6, 10,
53		-	scoreMatch4+bonusBoundarybonusFirstCharMultiplier+bonusBoundary*3)
	53	+	scoreMatch4+bonusBoundaryDelimiterbonusFirstCharMultiplier+bonusBoundaryDelimiter*3)
54	54		assertMatch(t, fn, false, forward, "/.oh-my-zsh/cache", "zshc", 8, 13,
55		-	scoreMatch4+bonusBoundarybonusFirstCharMultiplier+bonusBoundary*3+scoreGapStart)
	55	+	scoreMatch4+bonusBoundarybonusFirstCharMultiplier+bonusBoundary*2+scoreGapStart+bonusBoundaryDelimiter)
56	56		assertMatch(t, fn, false, forward, "ab0123 456", "12356", 3, 10,
57	57		scoreMatch5+bonusConsecutive3+scoreGapStart+scoreGapExtension)
58	58		assertMatch(t, fn, false, forward, "abc123 456", "12356", 3, 10,
59	59		scoreMatch5+bonusCamel123bonusFirstCharMultiplier+bonusCamel123*2+bonusConsecutive+scoreGapStart+scoreGapExtension)
60	60		assertMatch(t, fn, false, forward, "foo/bar/baz", "fbb", 0, 9,
61		-	scoreMatch3+bonusBoundarybonusFirstCharMultiplier+
62		-	bonusBoundary2+2scoreGapStart+4*scoreGapExtension)
	61	+	scoreMatch3+bonusBoundaryWhitebonusFirstCharMultiplier+
	62	+	bonusBoundaryDelimiter2+2scoreGapStart+4*scoreGapExtension)
63	63		assertMatch(t, fn, false, forward, "fooBarBaz", "fbb", 0, 7,
64		-	scoreMatch3+bonusBoundarybonusFirstCharMultiplier+
	64	+	scoreMatch3+bonusBoundaryWhitebonusFirstCharMultiplier+
65	65		bonusCamel1232+2scoreGapStart+2*scoreGapExtension)
66	66		assertMatch(t, fn, false, forward, "foo barbaz", "fbb", 0, 8,
67		-	scoreMatch3+bonusBoundarybonusFirstCharMultiplier+bonusBoundary+
	67	+	scoreMatch3+bonusBoundaryWhitebonusFirstCharMultiplier+bonusBoundaryWhite+
68	68		scoreGapStart2+scoreGapExtension3)
69	69		assertMatch(t, fn, false, forward, "fooBar Baz", "foob", 0, 4,
70		-	scoreMatch4+bonusBoundarybonusFirstCharMultiplier+bonusBoundary*3)
	70	+	scoreMatch4+bonusBoundaryWhitebonusFirstCharMultiplier+bonusBoundaryWhite*3)
71	71		assertMatch(t, fn, false, forward, "xFoo-Bar Baz", "foo-b", 1, 6,
72	72		scoreMatch5+bonusCamel123bonusFirstCharMultiplier+bonusCamel123*2+
73	73		bonusNonWord+bonusBoundary)
		skipped 1 lines
75	75		assertMatch(t, fn, true, forward, "fooBarbaz", "oBz", 2, 9,
76	76		scoreMatch3+bonusCamel123+scoreGapStart+scoreGapExtension3)
77	77		assertMatch(t, fn, true, forward, "Foo/Bar/Baz", "FBB", 0, 9,
78		-	scoreMatch3+bonusBoundary(bonusFirstCharMultiplier+2)+
	78	+	scoreMatch3+bonusBoundaryWhitebonusFirstCharMultiplier+bonusBoundaryDelimiter*2+
79	79		scoreGapStart2+scoreGapExtension4)
80	80		assertMatch(t, fn, true, forward, "FooBarBaz", "FBB", 0, 7,
81		-	scoreMatch3+bonusBoundarybonusFirstCharMultiplier+bonusCamel123*2+
	81	+	scoreMatch3+bonusBoundaryWhitebonusFirstCharMultiplier+bonusCamel123*2+
82	82		scoreGapStart2+scoreGapExtension2)
83	83		assertMatch(t, fn, true, forward, "FooBar Baz", "FooB", 0, 4,
84		-	scoreMatch4+bonusBoundarybonusFirstCharMultiplier+bonusBoundary*2+
85		-	util.Max(bonusCamel123, bonusBoundary))
	84	+	scoreMatch4+bonusBoundaryWhitebonusFirstCharMultiplier+bonusBoundaryWhite*2+
	85	+	util.Max(bonusCamel123, bonusBoundaryWhite))
86	86
87	87		// Consecutive bonus updated
88	88		assertMatch(t, fn, true, forward, "foo-bar", "o-ba", 2, 6,
		skipped 9 lines
98	98
99	99		func TestFuzzyMatchBackward(t *testing.T) {
100	100		assertMatch(t, FuzzyMatchV1, false, true, "foobar fb", "fb", 0, 4,
101		-	scoreMatch2+bonusBoundarybonusFirstCharMultiplier+
	101	+	scoreMatch2+bonusBoundaryWhitebonusFirstCharMultiplier+
102	102		scoreGapStart+scoreGapExtension)
103	103		assertMatch(t, FuzzyMatchV1, false, false, "foobar fb", "fb", 7, 9,
104		-	scoreMatch2+bonusBoundarybonusFirstCharMultiplier+bonusBoundary)
	104	+	scoreMatch2+bonusBoundaryWhitebonusFirstCharMultiplier+bonusBoundaryWhite)
105	105		}
106	106
107	107		func TestExactMatchNaive(t *testing.T) {
		skipped 6 lines
114	114		assertMatch(t, ExactMatchNaive, false, dir, "/AutomatorDocument.icns", "rdoc", 9, 13,
115	115		scoreMatch4+bonusCamel123+bonusConsecutive2)
116	116		assertMatch(t, ExactMatchNaive, false, dir, "/man1/zshcompctl.1", "zshc", 6, 10,
117		-	scoreMatch4+bonusBoundary(bonusFirstCharMultiplier+3))
	117	+	scoreMatch4+bonusBoundaryDelimiter(bonusFirstCharMultiplier+3))
118	118		assertMatch(t, ExactMatchNaive, false, dir, "/.oh-my-zsh/cache", "zsh/c", 8, 13,
119		-	scoreMatch5+bonusBoundary(bonusFirstCharMultiplier+4))
	119	+	scoreMatch5+bonusBoundary(bonusFirstCharMultiplier+3)+bonusBoundaryDelimiter)
120	120		}
121	121		}
122	122
		skipped 5 lines
128	128		}
129	129
130	130		func TestPrefixMatch(t *testing.T) {
131		-	score := (scoreMatch+bonusBoundary)3 + bonusBoundary(bonusFirstCharMultiplier-1)
	131	+	score := scoreMatch3 + bonusBoundaryWhitebonusFirstCharMultiplier + bonusBoundaryWhite*2
132	132
133	133		for _, dir := range []bool{true, false} {
134	134		assertMatch(t, PrefixMatch, true, dir, "fooBarbaz", "Foo", -1, -1, 0)
		skipped 21 lines
156	156		// Strip trailing white space from the string
157	157		assertMatch(t, SuffixMatch, false, dir, "fooBarbaz ", "baz", 6, 9,
158	158		scoreMatch3+bonusConsecutive2)
	159	+
159	160		// Only when the pattern doesn't end with a space
160	161		assertMatch(t, SuffixMatch, false, dir, "fooBarbaz ", "baz ", 6, 10,
161		-	scoreMatch4+bonusConsecutive2+bonusNonWord)
	162	+	scoreMatch4+bonusConsecutive2+bonusBoundaryWhite)
162	163		}
163	164		}
164	165
		skipped 17 lines
182	183		input, pattern, sidx, eidx, score)
183	184		}
184	185		}
185		-	test("Só Danço Samba", "So", 0, 2, 56, FuzzyMatchV1, FuzzyMatchV2, PrefixMatch, ExactMatchNaive)
186		-	test("Só Danço Samba", "sodc", 0, 7, 89, FuzzyMatchV1, FuzzyMatchV2)
187		-	test("Danço", "danco", 0, 5, 128, FuzzyMatchV1, FuzzyMatchV2, PrefixMatch, SuffixMatch, ExactMatchNaive, EqualMatch)
	186	+	test("Só Danço Samba", "So", 0, 2, 62, FuzzyMatchV1, FuzzyMatchV2, PrefixMatch, ExactMatchNaive)
	187	+	test("Só Danço Samba", "sodc", 0, 7, 97, FuzzyMatchV1, FuzzyMatchV2)
	188	+	test("Danço", "danco", 0, 5, 140, FuzzyMatchV1, FuzzyMatchV2, PrefixMatch, SuffixMatch, ExactMatchNaive, EqualMatch)
188	189		}
189	190
190	191		func TestLongString(t *testing.T) {
		skipped 8 lines