clerk/internal/lsp/fuzzy/fuzzy.go (view raw)
Oleksandr Smirnov
Oleksandr Smirnov
olexsmir@gmail.com perf: lsp: cut completion ranking allocations..., 1 month ago
olexsmir@gmail.com perf: lsp: cut completion ranking allocations..., 1 month ago
| 1 | package fuzzy |
| 2 | |
| 3 | import "strings" |
| 4 | |
| 5 | // Matcher scores a precompiled pattern against candidate texts; [Compile] |
| 6 | // hoists the lowercasing and rune conversion out of a per-candidate loop. |
| 7 | type Matcher struct { |
| 8 | p []rune // lowercased pattern runes; empty matches everything |
| 9 | } |
| 10 | |
| 11 | // Compile builds a matcher for pattern. The empty pattern matches every |
| 12 | // text with score 1. |
| 13 | func Compile(pattern string) Matcher { |
| 14 | if pattern == "" { |
| 15 | return Matcher{} |
| 16 | } |
| 17 | return Matcher{p: []rune(strings.ToLower(pattern))} |
| 18 | } |
| 19 | |
| 20 | // Score scores how well the pattern matches text as a subsequence. |
| 21 | // It returns 0 if pattern is not a case-insensitive subsequence of text, |
| 22 | // otherwise a score in (0, 1], where 1 is a perfect contiguous match at a |
| 23 | // segment boundary. An empty pattern matches everything with score 1. |
| 24 | // |
| 25 | // Matching is greedy and leftmost; each matched rune scores base 1, plus 3 if |
| 26 | // it starts a segment (text start or after a separator), plus 2 if it is |
| 27 | // contiguous with the previous matched rune, plus 1 if the case matches |
| 28 | // exactly. The total is normalized by 4L+1, the maximum score of a perfect |
| 29 | // match of length L, so exact segment matches score 1 regardless of length |
| 30 | // ("food" and "expenses" both match "expenses:food" at 1.0). |
| 31 | func (m Matcher) Score(text string) float64 { |
| 32 | p := m.p |
| 33 | if len(p) == 0 { |
| 34 | return 1 |
| 35 | } |
| 36 | t := []rune(text) |
| 37 | tl := []rune(strings.ToLower(text)) |
| 38 | |
| 39 | total := 0 |
| 40 | prev := -1 |
| 41 | for i, pr := range p { |
| 42 | j := prev + 1 |
| 43 | for ; j < len(t); j++ { |
| 44 | if tl[j] == pr { |
| 45 | break |
| 46 | } |
| 47 | } |
| 48 | if j == len(t) { |
| 49 | return 0 |
| 50 | } |
| 51 | w := 1 |
| 52 | if j == 0 || isFuzzySep(t[j-1]) { |
| 53 | w += 3 |
| 54 | } |
| 55 | if i > 0 && j == prev+1 { |
| 56 | w += 2 |
| 57 | } |
| 58 | if t[j] == p[i] { |
| 59 | w++ |
| 60 | } |
| 61 | total += w |
| 62 | prev = j |
| 63 | } |
| 64 | score := float64(total) / float64(4*len(p)+1) |
| 65 | if score > 1 { |
| 66 | return 1 |
| 67 | } |
| 68 | return score |
| 69 | } |
| 70 | |
| 71 | // Score scores pattern against text; see [Matcher.Score]. |
| 72 | func Score(pattern, text string) float64 { return Compile(pattern).Score(text) } |
| 73 | |
| 74 | // isFuzzySep reports whether r is a segment boundary for fuzzy matching: |
| 75 | // account-name separators and word boundaries. |
| 76 | func isFuzzySep(r rune) bool { |
| 77 | switch r { |
| 78 | case ':', '.', '-', '_', '/', ' ', '\t': |
| 79 | return true |
| 80 | } |
| 81 | return false |
| 82 | } |