1package palette
2
3import (
4 "sort"
5 "strings"
6 "unicode/utf8"
7)
8
9// Match is a fuzzy-matched immutable palette result.
10type Match struct {
11 Result Result
12 Positions []int
13 rank int
14 span int
15 first int
16 order int
17 search string
18}
19
20// Fuzzy searches immutable palette results.
21func Fuzzy(results []Result, query string) []Match {
22 needle := strings.ToLower(query)
23 if query == "" {
24 out := make([]Match, 0, len(results))
25 for i, result := range results {
26 out = append(out, newMatch(result, i))
27 }
28 return out
29 }
30
31 needleRunes := []rune(needle)
32 var out []Match
33 for i, result := range results {
34 if match, ok := score(result, needle, needleRunes, i); ok {
35 out = append(out, match)
36 }
37 }
38 sort.SliceStable(out, func(i, j int) bool {
39 a, b := out[i], out[j]
40 if a.rank != b.rank {
41 return a.rank < b.rank
42 }
43 if a.span != b.span {
44 return a.span < b.span
45 }
46 if a.first != b.first {
47 return a.first < b.first
48 }
49 if a.Result.Kind() != b.Result.Kind() {
50 return a.Result.Kind() < b.Result.Kind()
51 }
52 if a.search != b.search {
53 return a.search < b.search
54 }
55 return a.order < b.order
56 })
57 return out
58}
59
60func score(result Result, needle string, needleRunes []rune, order int) (Match, bool) {
61 match := newMatch(result, order)
62 text := match.search
63
64 // An exact command shortcode always wins over every other match. The
65 // remaining results then share exact/prefix/subsequence scoring.
66 if result.Kind() == ResultKindCommand && text == needle {
67 match.Positions = rangePositions(utf8.RuneCountInString(text))
68 match.rank, match.span, match.first = 0, len(match.Positions), 0
69 return match, true
70 }
71 if text == needle {
72 match.Positions = rangePositions(utf8.RuneCountInString(text))
73 match.rank, match.span, match.first = 1, len(match.Positions), 0
74 return match, true
75 }
76 if strings.HasPrefix(text, needle) {
77 match.Positions = rangePositions(utf8.RuneCountInString(needle))
78 match.rank, match.span, match.first = 2, len(match.Positions), 0
79 return match, true
80 }
81 if positions, ok := subsequencePositions([]rune(text), needleRunes); ok {
82 match.Positions = positions
83 match.rank, match.span, match.first = 3, positions[len(positions)-1]-positions[0]+1, positions[0]
84 return match, true
85 }
86 if cmd, ok := result.Command(); ok {
87 if positions, ok := subsequencePositions([]rune(strings.ToLower(cmd.Desc)), needleRunes); ok {
88 match.rank, match.span, match.first = 4, positions[len(positions)-1]-positions[0]+1, positions[0]
89 return match, true
90 }
91 }
92 return Match{}, false
93}
94
95func newMatch(result Result, order int) Match {
96 return Match{Result: result, order: order, search: strings.ToLower(result.SearchText())}
97}
98
99func rangePositions(n int) []int {
100 positions := make([]int, n)
101 for i := range positions {
102 positions[i] = i
103 }
104 return positions
105}
106
107func subsequencePositions(haystack, needle []rune) ([]int, bool) {
108 if len(needle) == 0 {
109 return nil, true
110 }
111 positions := make([]int, 0, len(needle))
112 j := 0
113 for i, r := range haystack {
114 if r == needle[j] {
115 positions = append(positions, i)
116 j++
117 if j == len(needle) {
118 return positions, true
119 }
120 }
121 }
122 return nil, false
123}