Repository: junegunn/fzf
Pull request #4252 (2025-02-17 11:29:01)

Normalize char before pattern lookup in FuzzyMatchV1
There is an edge-case in FuzzyMatchV1 during backward scan, related to normalization: if string is initially denormalized (e.g. Unicode symbol), backward scan will proceed further to the next char; however, when the score is computed, the string is normalized first, then scanned based on the pattern. This leads to accessing pattern index increment, which itself leads to out-of-bound index access, resulting in a panic.

To illustrate the process, here's the sequence of operations when search is perfored:

1. during backward scan by "minim" pattern

```
xxxxx Minímal example
      ^^^^^^^^^^^^
      ||||||||||||
      miniiiiiiiim <- compute score for this substring
```
2. during compute score by "minim" pattern
```
      Minímal exam
      minimal exam <- normalize chars before computing the score
      ^^^^^^
      ||||||
      minim <- at this point the pattern is already fully scanned and index
              is out-of-the-bound
```

In this commit the char is normalized during backward scan, to detect properly the boundaries for the pattern.

junegunn: Thanks, I can reproduce the problem.

```
echo 'Minímal example' | fzf --algo=v1 --tiebreak=end -f minim
panic: runtime error: index out of range [5] with length 5

goroutine 33 [running]:
github.com/junegunn/fzf/src/algo.calculateScore(0x0, 0x1, 0x14000246008, {0x1400023e030, 0x5, 0x0?}, 0x0, 0xc, 0x0)
        github.com/junegunn/fzf/src/algo/algo.go:674 +0x5f0
github.com/junegunn/fzf/src/algo.FuzzyMatchV1(0x0, 0x1, 0x0, 0x14000246008, {0x1400023e030, 0x5, 0x5}, 0x0, 0x0?)
        github.com/junegunn/fzf/src/algo/algo.go:785 +0x470
github.com/junegunn/fzf/src.(*Pattern).iter(0x0?, 0x102b7aec8, {0x1400011cc38?, 0x0?, 0x0?}, 0x0, 0x1, 0x0, {0x1400023e030, 0x5, ...}, ...)
        github.com/junegunn/fzf/src/pattern.go:448 +0xc4
github.com/junegunn/fzf/src.(*Pattern).extendedMatch(0x140002300b0, 0x14000246008?, 0x0, 0x14000226180)
        github.com/junegunn/fzf/src/pattern.go:394 +0x35c
github.com/junegunn/fzf/src.(*Pattern).MatchItem(0x140002300b0, 0x14000246008, 0x0?, 0x0?)
        github.com/junegunn/fzf/src/pattern.go:347 +0x30
github.com/junegunn/fzf/src.(*Pattern).matchChunk(0x140002300b0, 0x14000246008, {0x0?, 0x102b30860?, 0x0?}, 0x14000226180)
        github.com/junegunn/fzf/src/pattern.go:308 +0x3ac
github.com/junegunn/fzf/src.(*Pattern).Match(0x140002300b0, 0x14000246008, 0x14000226180)
        github.com/junegunn/fzf/src/pattern.go:293 +0x88
github.com/junegunn/fzf/src.(*Matcher).scan.func1(0x0, 0x14000226180, {0x14000224010, 0x1, 0x0?})
        github.com/junegunn/fzf/src/matcher.go:186 +0xf8
created by github.com/junegunn/fzf/src.(*Matcher).scan in goroutine 1
        github.com/junegunn/fzf/src/matcher.go:181 +0x4a8
```

Just out of curiosity, how did you find this problem?

Patch:
diff --git a/src/algo/algo.go b/src/algo/algo.go
index c0022475..d6a9a663 100644
--- a/src/algo/algo.go
+++ b/src/algo/algo.go
@@ -767,6 +767,9 @@ func FuzzyMatchV1(caseSensitive bool, normalize bool, forward bool, text *util.C
 					char = unicode.To(unicode.LowerCase, char)
 				}
 			}
+			if normalize {
+				char = normalizeRune(char)
+			}
 
 			pidx_ := indexAt(pidx, lenPattern, forward)
 			pchar := pattern[pidx_]


Test patch:
diff --git a/src/algo/algo_test.go b/src/algo/algo_test.go
index b5ed0e77..aab03b0a 100644
--- a/src/algo/algo_test.go
+++ b/src/algo/algo_test.go
@@ -200,3 +200,12 @@ func TestLongString(t *testing.T) {
 	bytes[math.MaxUint16] = 'z'
 	assertMatch(t, FuzzyMatchV2, true, true, string(bytes), "zx", math.MaxUint16, math.MaxUint16+2, scoreMatch*2+bonusConsecutive)
 }
+
+func TestLongStringWithNormalize(t *testing.T) {
+	bytes := make([]byte, 30000)
+	for i := range bytes {
+		bytes[i] = 'x'
+	}
+	unicodeString := string(bytes) + " Minímal example"
+	assertMatch2(t, FuzzyMatchV1, false, true, false, unicodeString, "minim", 30001, 30006, 140)
+}