1 package bytealg
2 3 import "testing"
4 5 // manualIndex is an independent scan, so the search functions are compared
6 // against something that shares no code with them.
7 func manualIndexRabinKarp(s, sep []byte) (r int32) {
8 if len(sep) == 0 {
9 return 0
10 }
11 for i := int32(0); i+len(sep) <= len(s); i++ {
12 match := true
13 for j := int32(0); j < len(sep); j++ {
14 if s[i+j] != sep[j] {
15 match = false
16 break
17 }
18 }
19 if match {
20 return i
21 }
22 }
23 return -1
24 }
25 26 func manualLastIndexRabinKarp(s, sep []byte) (r int32) {
27 r = -1
28 if len(sep) == 0 {
29 return int32(len(s))
30 }
31 for i := int32(0); i+len(sep) <= len(s); i++ {
32 match := true
33 for j := int32(0); j < len(sep); j++ {
34 if s[i+j] != sep[j] {
35 match = false
36 break
37 }
38 }
39 if match {
40 r = i
41 }
42 }
43 return
44 }
45 46 // TestRabinKarpMatchesBrute sweeps every offset of a haystack for a needle
47 // that is present and for one that is absent. Index's brute path hands over to
48 // bytealg.IndexRabinKarp once it has failed enough times
49 // (`fails >= 4+i>>4`), and the audit recorded a miss on that path: a manual
50 // scan found `"buckets":[1,` at offset 70 of a 132-byte buffer while
51 // bytes.Index answered -1. Both directions of the handover are checked here.
52 func TestRabinsKarpMatchesBrute(t *testing.T) {
53 sep := []byte("\"buckets\":[1,")
54 bad := int32(0)
55 for fill := byte('a'); fill <= byte('d'); fill++ {
56 for size := int32(0); size <= 180; size++ {
57 b := []byte{:size}
58 for i := int32(0); i < size; i++ {
59 b[i] = fill
60 }
61 for off := int32(0); off+int32(len(sep)) <= size; off++ {
62 // The needle is present at off.
63 for j := int32(0); j < int32(len(sep)); j++ {
64 b[off+j] = sep[j]
65 }
66 if w, g := manualIndexRabinKarp(b, sep), IndexRabinKarp(b, sep); w != g {
67 bad++
68 if bad < 5 {
69 t.Errorf("Index present size=%d off=%d: manual %d, Index %d", size, off, w, g)
70 }
71 }
72 if w, g := manualLastIndexRabinKarp(b, sep), LastIndexRabinKarp(b, sep); w != g {
73 bad++
74 if bad < 5 {
75 t.Errorf("LastIndex present size=%d off=%d: manual %d, LastIndex %d", size, off, w, g)
76 }
77 }
78 // The same haystack with the needle's last byte broken is a miss.
79 b[off+int32(len(sep))-1] = fill
80 if w, g := manualIndexRabinKarp(b, sep), IndexRabinKarp(b, sep); w != g {
81 bad++
82 if bad < 5 {
83 t.Errorf("Index absent size=%d off=%d: manual %d, Index %d", size, off, w, g)
84 }
85 }
86 if w, g := manualLastIndexRabinKarp(b, sep), LastIndexRabinKarp(b, sep); w != g {
87 bad++
88 if bad < 5 {
89 t.Errorf("LastIndex absent size=%d off=%d: manual %d, LastIndex %d", size, off, w, g)
90 }
91 }
92 // Restore for the next offset.
93 b[off+int32(len(sep))-1] = sep[len(sep)-1]
94 }
95 }
96 }
97 if bad > 0 {
98 t.Errorf("%d mismatches", bad)
99 }
100 }
101