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
63 identity, label, offset, hasTerms := result.searchTerms()
64 if hasTerms {
65 exactRank := 1
66 if result.Kind() == ResultKindCommand {
67 exactRank = 0
68 }
69 best, matched := scoreField(identity, needle, needleRunes, offset, exactRank, 2, 3)
70 if label != identity {
71 if candidate, ok := scoreField(label, needle, needleRunes, offset, exactRank, 2, 3); ok && (!matched || candidate.betterThan(best)) {
72 best, matched = candidate, true
73 }
74 }
75 if matched {
76 best.apply(&match)
77 return match, true
78 }
79 }
80
81 // Action text remains searchable, but semantic codes and session labels
82 // outrank matches caused only by a rendered action prefix.
83 if fallback, ok := scoreField(match.search, needle, needleRunes, 0, 4, 4, 4); ok {
84 fallback.apply(&match)
85 return match, true
86 }
87 if cmd, ok := result.Command(); ok {
88 if positions, ok := subsequencePositions([]rune(strings.ToLower(cmd.Desc)), needleRunes); ok {
89 match.rank, match.span, match.first = 5, positions[len(positions)-1]-positions[0]+1, positions[0]
90 return match, true
91 }
92 }
93 return Match{}, false
94}
95
96type fieldScore struct {
97 positions []int
98 rank int
99 span int
100 first int
101}
102
103func scoreField(text, needle string, needleRunes []rune, displayOffset, exactRank, prefixRank, subsequenceRank int) (fieldScore, bool) {
104 text = strings.ToLower(text)
105 var scored fieldScore
106 switch {
107 case text == needle:
108 scored.positions = rangePositions(utf8.RuneCountInString(text))
109 scored.rank = exactRank
110 case strings.HasPrefix(text, needle):
111 scored.positions = rangePositions(utf8.RuneCountInString(needle))
112 scored.rank = prefixRank
113 default:
114 positions, ok := subsequencePositions([]rune(text), needleRunes)
115 if !ok {
116 return fieldScore{}, false
117 }
118 scored.positions = positions
119 scored.rank = subsequenceRank
120 }
121 scored.span = scored.positions[len(scored.positions)-1] - scored.positions[0] + 1
122 scored.first = scored.positions[0]
123 for i := range scored.positions {
124 scored.positions[i] += displayOffset
125 }
126 return scored, true
127}
128
129func (s fieldScore) betterThan(other fieldScore) bool {
130 if s.rank != other.rank {
131 return s.rank < other.rank
132 }
133 if s.span != other.span {
134 return s.span < other.span
135 }
136 return s.first < other.first
137}
138
139func (s fieldScore) apply(match *Match) {
140 match.Positions = s.positions
141 match.rank = s.rank
142 match.span = s.span
143 match.first = s.first
144}
145
146func newMatch(result Result, order int) Match {
147 return Match{Result: result, order: order, search: strings.ToLower(result.SearchText())}
148}
149
150func rangePositions(n int) []int {
151 positions := make([]int, n)
152 for i := range positions {
153 positions[i] = i
154 }
155 return positions
156}
157
158func subsequencePositions(haystack, needle []rune) ([]int, bool) {
159 if len(needle) == 0 {
160 return nil, true
161 }
162 positions := make([]int, 0, len(needle))
163 j := 0
164 for i, r := range haystack {
165 if r == needle[j] {
166 positions = append(positions, i)
167 j++
168 if j == len(needle) {
169 return positions, true
170 }
171 }
172 }
173 return nil, false
174}