clerk/internal/lsp/fuzzy/fuzzy.go (view raw)
| 1 | package fuzzy |
| 2 | |
| 3 | import "strings" |
| 4 | |
| 5 | // Score scores how well pattern matches text as a subsequence. |
| 6 | // It returns 0 if pattern is not a case-insensitive subsequence of text, |
| 7 | // otherwise a score in (0, 1], where 1 is a perfect contiguous match at a |
| 8 | // segment boundary. An empty pattern matches everything with score 1. |
| 9 | // |
| 10 | // Matching is greedy and leftmost; each matched rune scores base 1, plus 3 if |
| 11 | // it starts a segment (text start or after a separator), plus 2 if it is |
| 12 | // contiguous with the previous matched rune, plus 1 if the case matches |
| 13 | // exactly. The total is normalized by 4L+1, the maximum score of a perfect |
| 14 | // match of length L, so exact segment matches score 1 regardless of length |
| 15 | // ("food" and "expenses" both match "expenses:food" at 1.0). |
| 16 | func Score(pattern, text string) float64 { |
| 17 | if pattern == "" { |
| 18 | return 1 |
| 19 | } |
| 20 | p := []rune(strings.ToLower(pattern)) |
| 21 | t := []rune(text) |
| 22 | tl := []rune(strings.ToLower(text)) |
| 23 | |
| 24 | total := 0 |
| 25 | prev := -1 |
| 26 | for i, pr := range p { |
| 27 | j := prev + 1 |
| 28 | for ; j < len(t); j++ { |
| 29 | if tl[j] == pr { |
| 30 | break |
| 31 | } |
| 32 | } |
| 33 | if j == len(t) { |
| 34 | return 0 |
| 35 | } |
| 36 | w := 1 |
| 37 | if j == 0 || isFuzzySep(t[j-1]) { |
| 38 | w += 3 |
| 39 | } |
| 40 | if i > 0 && j == prev+1 { |
| 41 | w += 2 |
| 42 | } |
| 43 | if t[j] == p[i] { |
| 44 | w++ |
| 45 | } |
| 46 | total += w |
| 47 | prev = j |
| 48 | } |
| 49 | score := float64(total) / float64(4*len(p)+1) |
| 50 | if score > 1 { |
| 51 | return 1 |
| 52 | } |
| 53 | return score |
| 54 | } |
| 55 | |
| 56 | // isFuzzySep reports whether r is a segment boundary for fuzzy matching: |
| 57 | // account-name separators and word boundaries. |
| 58 | func isFuzzySep(r rune) bool { |
| 59 | switch r { |
| 60 | case ':', '.', '-', '_', '/', ' ', '\t': |
| 61 | return true |
| 62 | } |
| 63 | return false |
| 64 | } |