1// Copyright (c) 2014, Suryandaru Triandana <syndtr@gmail.com>
2// All rights reserved.
3//
4// Use of this source code is governed by a BSD-style license that can be
5// found in the LICENSE file.
6
7package testutil
8
9import (
10	"fmt"
11	"math/rand"
12
13	. "github.com/onsi/gomega"
14
15	"github.com/syndtr/goleveldb/leveldb/iterator"
16)
17
18type IterAct int
19
20func (a IterAct) String() string {
21	switch a {
22	case IterNone:
23		return "none"
24	case IterFirst:
25		return "first"
26	case IterLast:
27		return "last"
28	case IterPrev:
29		return "prev"
30	case IterNext:
31		return "next"
32	case IterSeek:
33		return "seek"
34	case IterSOI:
35		return "soi"
36	case IterEOI:
37		return "eoi"
38	}
39	return "unknown"
40}
41
42const (
43	IterNone IterAct = iota
44	IterFirst
45	IterLast
46	IterPrev
47	IterNext
48	IterSeek
49	IterSOI
50	IterEOI
51)
52
53type IteratorTesting struct {
54	KeyValue
55	Iter         iterator.Iterator
56	Rand         *rand.Rand
57	PostFn       func(t *IteratorTesting)
58	Pos          int
59	Act, LastAct IterAct
60
61	once bool
62}
63
64func (t *IteratorTesting) init() {
65	if !t.once {
66		t.Pos = -1
67		t.once = true
68	}
69}
70
71func (t *IteratorTesting) post() {
72	if t.PostFn != nil {
73		t.PostFn(t)
74	}
75}
76
77func (t *IteratorTesting) setAct(act IterAct) {
78	t.LastAct, t.Act = t.Act, act
79}
80
81func (t *IteratorTesting) text() string {
82	return fmt.Sprintf("at pos %d and last action was <%v> -> <%v>", t.Pos, t.LastAct, t.Act)
83}
84
85func (t *IteratorTesting) Text() string {
86	return "IteratorTesting is " + t.text()
87}
88
89func (t *IteratorTesting) IsFirst() bool {
90	t.init()
91	return t.Len() > 0 && t.Pos == 0
92}
93
94func (t *IteratorTesting) IsLast() bool {
95	t.init()
96	return t.Len() > 0 && t.Pos == t.Len()-1
97}
98
99func (t *IteratorTesting) TestKV() {
100	t.init()
101	key, value := t.Index(t.Pos)
102	Expect(t.Iter.Key()).NotTo(BeNil())
103	Expect(t.Iter.Key()).Should(Equal(key), "Key is invalid, %s", t.text())
104	Expect(t.Iter.Value()).Should(Equal(value), "Value for key %q, %s", key, t.text())
105}
106
107func (t *IteratorTesting) First() {
108	t.init()
109	t.setAct(IterFirst)
110
111	ok := t.Iter.First()
112	Expect(t.Iter.Error()).ShouldNot(HaveOccurred())
113	if t.Len() > 0 {
114		t.Pos = 0
115		Expect(ok).Should(BeTrue(), t.Text())
116		t.TestKV()
117	} else {
118		t.Pos = -1
119		Expect(ok).ShouldNot(BeTrue(), t.Text())
120	}
121	t.post()
122}
123
124func (t *IteratorTesting) Last() {
125	t.init()
126	t.setAct(IterLast)
127
128	ok := t.Iter.Last()
129	Expect(t.Iter.Error()).ShouldNot(HaveOccurred())
130	if t.Len() > 0 {
131		t.Pos = t.Len() - 1
132		Expect(ok).Should(BeTrue(), t.Text())
133		t.TestKV()
134	} else {
135		t.Pos = 0
136		Expect(ok).ShouldNot(BeTrue(), t.Text())
137	}
138	t.post()
139}
140
141func (t *IteratorTesting) Next() {
142	t.init()
143	t.setAct(IterNext)
144
145	ok := t.Iter.Next()
146	Expect(t.Iter.Error()).ShouldNot(HaveOccurred())
147	if t.Pos < t.Len()-1 {
148		t.Pos++
149		Expect(ok).Should(BeTrue(), t.Text())
150		t.TestKV()
151	} else {
152		t.Pos = t.Len()
153		Expect(ok).ShouldNot(BeTrue(), t.Text())
154	}
155	t.post()
156}
157
158func (t *IteratorTesting) Prev() {
159	t.init()
160	t.setAct(IterPrev)
161
162	ok := t.Iter.Prev()
163	Expect(t.Iter.Error()).ShouldNot(HaveOccurred())
164	if t.Pos > 0 {
165		t.Pos--
166		Expect(ok).Should(BeTrue(), t.Text())
167		t.TestKV()
168	} else {
169		t.Pos = -1
170		Expect(ok).ShouldNot(BeTrue(), t.Text())
171	}
172	t.post()
173}
174
175func (t *IteratorTesting) Seek(i int) {
176	t.init()
177	t.setAct(IterSeek)
178
179	key, _ := t.Index(i)
180	oldKey, _ := t.IndexOrNil(t.Pos)
181
182	ok := t.Iter.Seek(key)
183	Expect(t.Iter.Error()).ShouldNot(HaveOccurred())
184	Expect(ok).Should(BeTrue(), fmt.Sprintf("Seek from key %q to %q, to pos %d, %s", oldKey, key, i, t.text()))
185
186	t.Pos = i
187	t.TestKV()
188	t.post()
189}
190
191func (t *IteratorTesting) SeekInexact(i int) {
192	t.init()
193	t.setAct(IterSeek)
194	var key0 []byte
195	key1, _ := t.Index(i)
196	if i > 0 {
197		key0, _ = t.Index(i - 1)
198	}
199	key := BytesSeparator(key0, key1)
200	oldKey, _ := t.IndexOrNil(t.Pos)
201
202	ok := t.Iter.Seek(key)
203	Expect(t.Iter.Error()).ShouldNot(HaveOccurred())
204	Expect(ok).Should(BeTrue(), fmt.Sprintf("Seek from key %q to %q (%q), to pos %d, %s", oldKey, key, key1, i, t.text()))
205
206	t.Pos = i
207	t.TestKV()
208	t.post()
209}
210
211func (t *IteratorTesting) SeekKey(key []byte) {
212	t.init()
213	t.setAct(IterSeek)
214	oldKey, _ := t.IndexOrNil(t.Pos)
215	i := t.Search(key)
216
217	ok := t.Iter.Seek(key)
218	Expect(t.Iter.Error()).ShouldNot(HaveOccurred())
219	if i < t.Len() {
220		key_, _ := t.Index(i)
221		Expect(ok).Should(BeTrue(), fmt.Sprintf("Seek from key %q to %q (%q), to pos %d, %s", oldKey, key, key_, i, t.text()))
222		t.Pos = i
223		t.TestKV()
224	} else {
225		Expect(ok).ShouldNot(BeTrue(), fmt.Sprintf("Seek from key %q to %q, %s", oldKey, key, t.text()))
226	}
227
228	t.Pos = i
229	t.post()
230}
231
232func (t *IteratorTesting) SOI() {
233	t.init()
234	t.setAct(IterSOI)
235	Expect(t.Pos).Should(BeNumerically("<=", 0), t.Text())
236	for i := 0; i < 3; i++ {
237		t.Prev()
238	}
239	t.post()
240}
241
242func (t *IteratorTesting) EOI() {
243	t.init()
244	t.setAct(IterEOI)
245	Expect(t.Pos).Should(BeNumerically(">=", t.Len()-1), t.Text())
246	for i := 0; i < 3; i++ {
247		t.Next()
248	}
249	t.post()
250}
251
252func (t *IteratorTesting) WalkPrev(fn func(t *IteratorTesting)) {
253	t.init()
254	for old := t.Pos; t.Pos > 0; old = t.Pos {
255		fn(t)
256		Expect(t.Pos).Should(BeNumerically("<", old), t.Text())
257	}
258}
259
260func (t *IteratorTesting) WalkNext(fn func(t *IteratorTesting)) {
261	t.init()
262	for old := t.Pos; t.Pos < t.Len()-1; old = t.Pos {
263		fn(t)
264		Expect(t.Pos).Should(BeNumerically(">", old), t.Text())
265	}
266}
267
268func (t *IteratorTesting) PrevAll() {
269	t.WalkPrev(func(t *IteratorTesting) {
270		t.Prev()
271	})
272}
273
274func (t *IteratorTesting) NextAll() {
275	t.WalkNext(func(t *IteratorTesting) {
276		t.Next()
277	})
278}
279
280func DoIteratorTesting(t *IteratorTesting) {
281	if t.Rand == nil {
282		t.Rand = NewRand()
283	}
284	t.SOI()
285	t.NextAll()
286	t.First()
287	t.SOI()
288	t.NextAll()
289	t.EOI()
290	t.PrevAll()
291	t.Last()
292	t.EOI()
293	t.PrevAll()
294	t.SOI()
295
296	t.NextAll()
297	t.PrevAll()
298	t.NextAll()
299	t.Last()
300	t.PrevAll()
301	t.First()
302	t.NextAll()
303	t.EOI()
304
305	ShuffledIndex(t.Rand, t.Len(), 1, func(i int) {
306		t.Seek(i)
307	})
308
309	ShuffledIndex(t.Rand, t.Len(), 1, func(i int) {
310		t.SeekInexact(i)
311	})
312
313	ShuffledIndex(t.Rand, t.Len(), 1, func(i int) {
314		t.Seek(i)
315		if i%2 != 0 {
316			t.PrevAll()
317			t.SOI()
318		} else {
319			t.NextAll()
320			t.EOI()
321		}
322	})
323
324	for _, key := range []string{"", "foo", "bar", "\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff"} {
325		t.SeekKey([]byte(key))
326	}
327}
328