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