1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 package compact
16
17 import (
18 "fmt"
19 "strings"
20 "testing"
21 )
22
23 var factory = &RangeFactory{Hash: func(_, _ []byte) []byte {
24 return []byte("fake-hash")
25 }}
26
27 func TestAppendRangeErrors(t *testing.T) {
28 anotherFactory := &RangeFactory{Hash: factory.Hash}
29
30 nonEmpty1, _ := factory.NewRange(7, 8, [][]byte{[]byte("hash")})
31 nonEmpty2, _ := factory.NewRange(0, 6, [][]byte{[]byte("hash0"), []byte("hash1")})
32 nonEmpty3, _ := factory.NewRange(6, 7, [][]byte{[]byte("hash")})
33 corrupt := func(rng *Range, dBegin, dEnd int64) *Range {
34 rng.begin = uint64(int64(rng.begin) + dBegin)
35 rng.end = uint64(int64(rng.end) + dEnd)
36 return rng
37 }
38 for _, tc := range []struct {
39 desc string
40 l, r *Range
41 wantErr string
42 }{
43 {
44 desc: "ok",
45 l: factory.NewEmptyRange(0),
46 r: factory.NewEmptyRange(0),
47 },
48 {
49 desc: "incompatible",
50 l: factory.NewEmptyRange(0),
51 r: anotherFactory.NewEmptyRange(0),
52 wantErr: "incompatible ranges",
53 },
54 {
55 desc: "disjoint",
56 l: factory.NewEmptyRange(0),
57 r: factory.NewEmptyRange(1),
58 wantErr: "ranges are disjoint",
59 },
60 {
61 desc: "left_corrupted",
62 l: corrupt(factory.NewEmptyRange(7), -7, 0),
63 r: nonEmpty1,
64 wantErr: "corrupted lhs range",
65 },
66 {
67 desc: "right_corrupted",
68 l: nonEmpty2,
69 r: corrupt(nonEmpty3, 0, 20),
70 wantErr: "corrupted rhs range",
71 },
72 } {
73 t.Run(tc.desc, func(t *testing.T) {
74 err := tc.l.AppendRange(tc.r, nil)
75 if tc.wantErr == "" {
76 if err != nil {
77 t.Fatalf("AppendRange: %v; want nil", err)
78 }
79 } else if err == nil || !strings.HasPrefix(err.Error(), tc.wantErr) {
80 t.Fatalf("AppendRange: %v; want containing %q", err, tc.wantErr)
81 }
82 })
83 }
84 }
85
86 func TestEqual(t *testing.T) {
87 for _, test := range []struct {
88 desc string
89 lhs *Range
90 rhs *Range
91 wantEqual bool
92 }{
93 {
94 desc: "incompatible trees",
95 lhs: &Range{
96 f: factory,
97 begin: 17,
98 end: 23,
99 hashes: [][]byte{[]byte("hash 1"), []byte("hash 2")},
100 },
101 rhs: &Range{
102 f: &RangeFactory{Hash: factory.Hash},
103 begin: 17,
104 end: 23,
105 hashes: [][]byte{[]byte("hash 1"), []byte("hash 2")},
106 },
107 },
108
109 {
110 desc: "unequal begin",
111 lhs: &Range{
112 f: factory,
113 begin: 17,
114 end: 23,
115 hashes: [][]byte{[]byte("hash 1"), []byte("hash 2")},
116 },
117 rhs: &Range{
118 f: factory,
119 begin: 18,
120 end: 23,
121 hashes: [][]byte{[]byte("hash 1"), []byte("hash 2")},
122 },
123 },
124
125 {
126 desc: "unequal end",
127 lhs: &Range{
128 f: factory,
129 begin: 17,
130 end: 23,
131 hashes: [][]byte{[]byte("hash 1"), []byte("hash 2")},
132 },
133 rhs: &Range{
134 f: factory,
135 begin: 17,
136 end: 24,
137 hashes: [][]byte{[]byte("hash 1"), []byte("hash 2")},
138 },
139 },
140
141 {
142 desc: "unequal number of hashes",
143 lhs: &Range{
144 f: factory,
145 begin: 17,
146 end: 23,
147 hashes: [][]byte{[]byte("hash 1"), []byte("hash 2")},
148 },
149 rhs: &Range{
150 f: factory,
151 begin: 17,
152 end: 23,
153 hashes: [][]byte{[]byte("hash 1")},
154 },
155 },
156
157 {
158 desc: "mismatched hash",
159 lhs: &Range{
160 f: factory,
161 begin: 17,
162 end: 23,
163 hashes: [][]byte{[]byte("hash 1"), []byte("hash 2")},
164 },
165 rhs: &Range{
166 f: factory,
167 begin: 17,
168 end: 23,
169 hashes: [][]byte{[]byte("hash 1"), []byte("not hash 2")},
170 },
171 },
172
173 {
174 desc: "equal ranges",
175 lhs: &Range{
176 f: factory,
177 begin: 17,
178 end: 23,
179 hashes: [][]byte{[]byte("hash 1"), []byte("hash 2")},
180 },
181 rhs: &Range{
182 f: factory,
183 begin: 17,
184 end: 23,
185 hashes: [][]byte{[]byte("hash 1"), []byte("hash 2")},
186 },
187 wantEqual: true,
188 },
189 } {
190 t.Run(test.desc, func(t *testing.T) {
191 if got, want := test.lhs.Equal(test.rhs), test.wantEqual; got != want {
192 t.Errorf("%+v.Equal(%+v) = %v, want %v", test.lhs, test.rhs, got, want)
193 }
194 })
195 }
196 }
197
198 func TestGetMergePath(t *testing.T) {
199 for _, tc := range []struct {
200 begin, mid, end uint64
201 wantLow uint
202 wantHigh uint
203 wantEmpty bool
204 }{
205 {begin: 0, mid: 0, end: 0, wantEmpty: true},
206 {begin: 0, mid: 0, end: 1, wantEmpty: true},
207 {begin: 0, mid: 0, end: uint64(1) << 63, wantEmpty: true},
208 {begin: 0, mid: 1, end: 1, wantEmpty: true},
209 {begin: 0, mid: 1, end: 2, wantLow: 0, wantHigh: 1},
210 {begin: 0, mid: 16, end: 32, wantLow: 4, wantHigh: 5},
211 {begin: 0, mid: uint64(1) << 63, end: ^uint64(0), wantEmpty: true},
212 {begin: 0, mid: uint64(1) << 63, end: uint64(1)<<63 + 100500, wantEmpty: true},
213 {begin: 2, mid: 9, end: 13, wantLow: 0, wantHigh: 2},
214 {begin: 6, mid: 13, end: 17, wantLow: 0, wantHigh: 3},
215 {begin: 4, mid: 8, end: 16, wantEmpty: true},
216 {begin: 8, mid: 12, end: 16, wantLow: 2, wantHigh: 3},
217 {begin: 4, mid: 6, end: 12, wantLow: 1, wantHigh: 2},
218 {begin: 8, mid: 10, end: 16, wantLow: 1, wantHigh: 3},
219 {begin: 11, mid: 17, end: 27, wantLow: 0, wantHigh: 3},
220 {begin: 11, mid: 16, end: 27, wantEmpty: true},
221 } {
222 t.Run(fmt.Sprintf("%d:%d:%d", tc.begin, tc.mid, tc.end), func(t *testing.T) {
223 low, high := getMergePath(tc.begin, tc.mid, tc.end)
224 if tc.wantEmpty {
225 if low < high {
226 t.Fatalf("getMergePath(%d,%d,%d)=%d,%d; want empty", tc.begin, tc.mid, tc.end, low, high)
227 }
228 } else if low != tc.wantLow || high != tc.wantHigh {
229 t.Fatalf("getMergePath(%d,%d,%d)=%d,%d; want %d,%d", tc.begin, tc.mid, tc.end, low, high, tc.wantLow, tc.wantHigh)
230 }
231 })
232 }
233 }
234
View as plain text