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