1// Package fuzzy scores one already case-folded text against a folded query.
2//
3// A field matches exactly, by prefix, or as an in-order rune subsequence.
4// Callers map each Kind to their own rank and order matches with Less.
5package fuzzy
6
7import "strings"
8
9// Kind is how a field matched the query.
10type Kind uint8
11
12// Kinds are ordered best first, so a caller may use the Kind itself as a rank.
13const (
14 Exact Kind = iota
15 Prefix
16 Subsequence
17)
18
19// Score is one field match. Positions are rune indexes into the text.
20type Score struct {
21 Kind Kind
22 Positions []int
23 // Span is the rune distance from the first to the last matched position.
24 Span int
25 First int
26}
27
28// Match scores folded text against query, whose runes are needle. An empty
29// needle matches as Exact with no positions.
30func Match(text, query string, needle []rune) (Score, bool) {
31 if len(needle) == 0 {
32 return Score{Kind: Exact}, true
33 }
34 var score Score
35 switch {
36 case text == query:
37 score = Score{Kind: Exact, Positions: rangePositions(len(needle))}
38 case strings.HasPrefix(text, query):
39 score = Score{Kind: Prefix, Positions: rangePositions(len(needle))}
40 default:
41 positions, ok := subsequencePositions([]rune(text), needle)
42 if !ok {
43 return Score{}, false
44 }
45 score = Score{Kind: Subsequence, Positions: positions}
46 }
47 score.Span = score.Positions[len(score.Positions)-1] - score.Positions[0] + 1
48 score.First = score.Positions[0]
49 return score, true
50}
51
52// Less orders two scores whose ranks the caller derived from their Kind:
53// lower rank, then tighter span, then earlier first position.
54func Less(leftRank int, left Score, rightRank int, right Score) bool {
55 if leftRank != rightRank {
56 return leftRank < rightRank
57 }
58 if left.Span != right.Span {
59 return left.Span < right.Span
60 }
61 return left.First < right.First
62}
63
64// rangePositions returns the positions 0..n-1.
65func rangePositions(n int) []int {
66 positions := make([]int, n)
67 for i := range positions {
68 positions[i] = i
69 }
70 return positions
71}
72
73// subsequencePositions returns the first in-order positions of needle in
74// haystack.
75func subsequencePositions(haystack, needle []rune) ([]int, bool) {
76 if len(needle) == 0 {
77 return nil, true
78 }
79 positions := make([]int, 0, len(needle))
80 next := 0
81 for idx, r := range haystack {
82 if r != needle[next] {
83 continue
84 }
85 positions = append(positions, idx)
86 next++
87 if next == len(needle) {
88 return positions, true
89 }
90 }
91 return nil, false
92}