ahocorasick_test.gno
8.34 Kb · 260 lines
1package ahocorasick
2
3import (
4 "strings"
5 "testing"
6
7 "gno.land/p/nt/uassert/v0"
8)
9
10// fmtMatches renders a match slice as "start:end:pattern" joined by spaces, so
11// a failing case prints the whole scan instead of the first difference.
12func fmtMatches(ms []Match) string {
13 parts := make([]string, 0, len(ms))
14 for _, m := range ms {
15 parts = append(parts, itoa(m.Start)+":"+itoa(m.End)+":"+m.Pattern)
16 }
17 return strings.Join(parts, " ")
18}
19
20func itoa(n int) string {
21 if n == 0 {
22 return "0"
23 }
24 var b []byte
25 for n > 0 {
26 b = append([]byte{byte('0' + n%10)}, b...)
27 n /= 10
28 }
29 return string(b)
30}
31
32func TestFindAll(t *testing.T) {
33 cases := []struct {
34 name string
35 patterns []string
36 text string
37 want string
38 }{
39 {
40 // The textbook automaton from the 1975 paper.
41 name: "ushers",
42 patterns: []string{"he", "she", "his", "hers"},
43 text: "ushers",
44 want: "1:4:she 2:4:he 2:6:hers",
45 },
46 {
47 // Every suffix of the longest pattern is also a pattern, so one
48 // position must report four matches through the output links.
49 name: "nested suffixes",
50 patterns: []string{"abcd", "bcd", "cd", "d"},
51 text: "abcd",
52 want: "0:4:abcd 1:4:bcd 2:4:cd 3:4:d",
53 },
54 {
55 name: "overlapping",
56 patterns: []string{"a", "ab", "bab", "bc", "bca", "c", "caa"},
57 text: "abccab",
58 want: "0:1:a 0:2:ab 1:3:bc 2:3:c 3:4:c 4:5:a 4:6:ab",
59 },
60 {
61 name: "no match",
62 patterns: []string{"xyz", "qq"},
63 text: "the quick brown fox",
64 want: "",
65 },
66 {
67 name: "empty text",
68 patterns: []string{"a"},
69 text: "",
70 want: "",
71 },
72 {
73 // A pattern longer than the text can never match, and must not
74 // walk the automaton off its end trying.
75 name: "pattern longer than text",
76 patterns: []string{"abcdef"},
77 text: "abc",
78 want: "",
79 },
80 {
81 name: "repeats",
82 patterns: []string{"aa"},
83 text: "aaaa",
84 want: "0:2:aa 1:3:aa 2:4:aa",
85 },
86 {
87 // The empty pattern matches everywhere and nowhere; it is dropped
88 // rather than reported at every offset.
89 name: "empty pattern dropped",
90 patterns: []string{"", "b"},
91 text: "abc",
92 want: "1:2:b",
93 },
94 }
95 for _, tc := range cases {
96 t.Run(tc.name, func(t *testing.T) {
97 got := fmtMatches(New(tc.patterns).FindAll(tc.text))
98 uassert.Equal(t, tc.want, got)
99 })
100 }
101}
102
103// At one end offset the longest match comes first, because the scan reports
104// the node it reached before walking the output links to its shorter
105// suffixes. A caller taking the first match per offset gets the greedy one.
106func TestFindAllOrdersLongestFirstAtAnEndOffset(t *testing.T) {
107 got := New([]string{"he", "she"}).FindAll("she")
108 uassert.Equal(t, "0:3:she 1:3:he", fmtMatches(got))
109}
110
111// The index is the caller's slot in the pattern slice, not the automaton's
112// node number: that is what lets a caller map a match back to whatever it
113// stored alongside the pattern.
114func TestMatchIndexIsTheCallersSlot(t *testing.T) {
115 ms := New([]string{"zz", "he", "qq"}).FindAll("he")
116 uassert.Equal(t, 1, len(ms))
117 uassert.Equal(t, 1, ms[0].Index)
118 uassert.Equal(t, "he", ms[0].Pattern)
119}
120
121// A duplicated pattern is two slots, so it reports twice. Deduplicating here
122// would silently drop the second caller's payload.
123func TestDuplicatePatternsReportOnceperSlot(t *testing.T) {
124 ms := New([]string{"ab", "ab"}).FindAll("ab")
125 uassert.Equal(t, 2, len(ms))
126 uassert.Equal(t, 0, ms[0].Index)
127 uassert.Equal(t, 1, ms[1].Index)
128}
129
130func TestFindFirst(t *testing.T) {
131 m, ok := New([]string{"brown", "fox"}).FindFirst("the quick brown fox")
132 uassert.True(t, ok)
133 uassert.Equal(t, "brown", m.Pattern)
134 uassert.Equal(t, 10, m.Start)
135
136 _, ok = New([]string{"cat"}).FindFirst("the quick brown fox")
137 uassert.False(t, ok)
138}
139
140// FindFirst stops at the first match, so it must agree with FindAll's head
141// rather than with some other traversal order.
142func TestFindFirstAgreesWithFindAll(t *testing.T) {
143 m := New([]string{"he", "she", "hers"})
144 all := m.FindAll("ushers")
145 first, ok := m.FindFirst("ushers")
146 uassert.True(t, ok)
147 uassert.Equal(t, all[0].Start, first.Start)
148 uassert.Equal(t, all[0].Pattern, first.Pattern)
149}
150
151func TestContains(t *testing.T) {
152 m := New([]string{"spam", "eggs"})
153 uassert.True(t, m.Contains("green eggs and ham"))
154 uassert.False(t, m.Contains("green ham"))
155}
156
157// Matching is over BYTES. UTF-8 is self-synchronizing, so a pattern that is
158// itself valid UTF-8 can only match on a rune boundary of valid UTF-8 text.
159func TestValidUTF8PatternMatchesOnARuneBoundary(t *testing.T) {
160 ms := New([]string{"é"}).FindAll("café")
161 uassert.Equal(t, "3:5:é", fmtMatches(ms))
162}
163
164// The flip side of the same fact, and the reason the doc says bytes: a
165// pattern that is a bare continuation byte DOES match inside a rune. A caller
166// slicing on that offset splits the rune.
167func TestContinuationBytePatternMatchesInsideARune(t *testing.T) {
168 ms := New([]string{"\xa9"}).FindAll("café")
169 uassert.Equal(t, 1, len(ms))
170 uassert.Equal(t, 4, ms[0].Start)
171}
172
173// Refusals. The bounds exist so an on-chain caller cannot be handed an
174// unbounded build; a refusal is nil, and nil still answers every query.
175func TestNewRefusesWhatItCannotBound(t *testing.T) {
176 uassert.True(t, New(nil) == nil)
177 uassert.True(t, New([]string{}) == nil)
178 uassert.True(t, New([]string{"", ""}) == nil)
179
180 tooMany := make([]string, MaxPatterns+1)
181 for i := range tooMany {
182 tooMany[i] = "p" + itoa(i)
183 }
184 uassert.True(t, New(tooMany) == nil)
185
186 uassert.True(t, New([]string{strings.Repeat("a", MaxPatternLen+1)}) == nil)
187 uassert.True(t, New([]string{strings.Repeat("a", MaxPatternLen)}) != nil)
188}
189
190// A nil matcher is what a refused build returns, so every method has to
191// survive it: a demo that renders whatever New gave it must not panic.
192func TestNilMatcherAnswersEverything(t *testing.T) {
193 var m *Matcher
194 uassert.Equal(t, 0, len(m.FindAll("anything")))
195 uassert.False(t, m.Contains("anything"))
196 _, ok := m.FindFirst("anything")
197 uassert.False(t, ok)
198 uassert.Equal(t, 0, len(m.Patterns()))
199 uassert.Equal(t, 0, m.Nodes())
200}
201
202// Patterns returns the accepted set, empties dropped, in the caller's order,
203// and the returned slice is a copy: mutating it must not corrupt the
204// automaton's own view of what it matched.
205func TestPatternsIsACopyOfTheAcceptedSet(t *testing.T) {
206 m := New([]string{"he", "", "she"})
207 got := m.Patterns()
208 uassert.Equal(t, "he she", strings.Join(got, " "))
209 got[0] = "clobbered"
210 uassert.Equal(t, "he she", strings.Join(m.Patterns(), " "))
211}
212
213// The automaton is one node per distinct pattern prefix plus the root, which
214// is what makes the build linear in the total pattern length rather than in
215// the product of the set.
216func TestNodesCountsDistinctPrefixesPlusTheRoot(t *testing.T) {
217 // he, she, his, hers: prefixes h, he, her, hers, s, sh, she, hi, his = 9.
218 uassert.Equal(t, 10, New([]string{"he", "she", "his", "hers"}).Nodes())
219 // A single pattern is its own prefix chain.
220 uassert.Equal(t, 4, New([]string{"abc"}).Nodes())
221}
222
223// The guarantee worth having over a naive scan: the text cursor never moves
224// backwards, so a pathological set cannot be made to cost more than one pass.
225// 64 patterns that all share a prefix, over a text of the same letter.
226func TestPathologicalSetStaysOnePass(t *testing.T) {
227 patterns := make([]string, 0, 64)
228 for i := 1; i <= 64; i++ {
229 patterns = append(patterns, strings.Repeat("a", i))
230 }
231 ms := New(patterns).FindAll(strings.Repeat("a", 64))
232 // Every (start, length) pair with start+length <= 64: 64*65/2.
233 uassert.Equal(t, 2080, len(ms))
234}
235
236// The merged output lists are what the package doc calls its one departure
237// from the paper, so the shape that costs the most is pinned rather than
238// asserted in prose. A nested set of k patterns stores 1+2+...+k entries,
239// quadratic in k, where a dictionary of distinct words stores one per node.
240func TestMergedOutputsAreQuadraticOnANestedSet(t *testing.T) {
241 nested := make([]string, 0, 64)
242 for i := 1; i <= 64; i++ {
243 nested = append(nested, strings.Repeat("a", i))
244 }
245 uassert.Equal(t, 2080, totalOutputs(New(nested)))
246
247 // Four distinct words, no nesting: one entry per terminal node.
248 uassert.Equal(t, 4, totalOutputs(New([]string{"fox", "lazy", "over", "quick"})))
249
250 // he/she/his/hers nests once, "he" inside "she", so one node carries two.
251 uassert.Equal(t, 5, totalOutputs(New([]string{"he", "she", "his", "hers"})))
252}
253
254func totalOutputs(m *Matcher) int {
255 n := 0
256 for _, nd := range m.nodes {
257 n += len(nd.out)
258 }
259 return n
260}
