1//  Copyright (c) 2017 Couchbase, Inc.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// 		http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15package vellum
16
17import (
18	"bytes"
19	"io/ioutil"
20	"os"
21	"reflect"
22	"testing"
23)
24
25func TestRoundTripSimple(t *testing.T) {
26	f, err := ioutil.TempFile("", "vellum")
27	if err != nil {
28		t.Fatal(err)
29	}
30	defer func() {
31		err = f.Close()
32		if err != nil {
33			t.Fatal(err)
34		}
35	}()
36	defer func() {
37		err = os.Remove(f.Name())
38		if err != nil {
39			t.Fatal(err)
40		}
41	}()
42
43	b, err := New(f, nil)
44	if err != nil {
45		t.Fatalf("error creating builder: %v", err)
46	}
47
48	err = insertStringMap(b, smallSample)
49	if err != nil {
50		t.Fatalf("error building: %v", err)
51	}
52
53	err = b.Close()
54	if err != nil {
55		t.Fatalf("err closing: %v", err)
56	}
57
58	fst, err := Open(f.Name())
59	if err != nil {
60		t.Fatalf("error loading set: %v", err)
61	}
62	defer func() {
63		err = fst.Close()
64		if err != nil {
65			t.Fatal(err)
66		}
67	}()
68
69	// first check all the expected values
70	got := map[string]uint64{}
71	itr, err := fst.Iterator(nil, nil)
72	for err == nil {
73		key, val := itr.Current()
74		got[string(key)] = val
75		err = itr.Next()
76	}
77	if err != ErrIteratorDone {
78		t.Errorf("iterator error: %v", err)
79	}
80	if !reflect.DeepEqual(smallSample, got) {
81		t.Errorf("expected %v, got: %v", smallSample, got)
82	}
83
84	// some additional tests for items that should not exist
85	if ok, _ := fst.Contains([]byte("mo")); ok {
86		t.Errorf("expected to not contain mo, but did")
87	}
88
89	if ok, _ := fst.Contains([]byte("monr")); ok {
90		t.Errorf("expected to not contain monr, but did")
91	}
92
93	if ok, _ := fst.Contains([]byte("thur")); ok {
94		t.Errorf("expected to not contain thur, but did")
95	}
96
97	if ok, _ := fst.Contains([]byte("thurp")); ok {
98		t.Errorf("expected to not contain thurp, but did")
99	}
100
101	if ok, _ := fst.Contains([]byte("tue")); ok {
102		t.Errorf("expected to not contain tue, but did")
103	}
104
105	if ok, _ := fst.Contains([]byte("tuesd")); ok {
106		t.Errorf("expected to not contain tuesd, but did")
107	}
108
109	// a few more misc non-existent values to increase coverage
110	if ok, _ := fst.Contains([]byte("x")); ok {
111		t.Errorf("expected to not contain x, but did")
112	}
113
114	// now try accessing it through the Automaton interface
115	exists := AutomatonContains(fst, []byte("mon"))
116	if !exists {
117		t.Errorf("expected key 'mon' to exist, doesn't")
118	}
119
120	exists = AutomatonContains(fst, []byte("mons"))
121	if exists {
122		t.Errorf("expected key 'mo' to not exist, does")
123	}
124
125	// now try accessing it through the Transducer interface
126	var val uint64
127	exists, val = TransducerGet(fst, []byte("mon"))
128	if !exists {
129		t.Errorf("expected key 'mon' to exist, doesn't")
130	}
131	if val != 2 {
132		t.Errorf("expected val 2, got %d", val)
133	}
134
135	// now try accessing it through the Transducer interface
136	// for key that doesn't exist
137	exists, _ = TransducerGet(fst, []byte("mons"))
138	if exists {
139		t.Errorf("expected key 'mo' to not exist, does")
140	}
141}
142
143func TestRoundTripThousand(t *testing.T) {
144	dataset := thousandTestWords
145	randomThousandVals := randomValues(dataset)
146
147	f, err := ioutil.TempFile("", "vellum")
148	if err != nil {
149		t.Fatal(err)
150	}
151	defer func() {
152		err = f.Close()
153		if err != nil {
154			t.Fatal(err)
155		}
156	}()
157	defer func() {
158		err = os.Remove(f.Name())
159		if err != nil {
160			t.Fatal(err)
161		}
162	}()
163
164	b, err := New(f, nil)
165	if err != nil {
166		t.Fatalf("error creating builder: %v", err)
167	}
168
169	err = insertStrings(b, dataset, randomThousandVals)
170	if err != nil {
171		t.Fatalf("error inserting thousand words: %v", err)
172	}
173	err = b.Close()
174	if err != nil {
175		t.Fatalf("error closing builder: %v", err)
176	}
177
178	fst, err := Open(f.Name())
179	if err != nil {
180		t.Fatalf("error loading set: %v", err)
181	}
182	defer func() {
183		err = fst.Close()
184		if err != nil {
185			t.Fatal(err)
186		}
187	}()
188
189	// first check all the expected values
190	got := map[string]uint64{}
191	itr, err := fst.Iterator(nil, nil)
192	for err == nil {
193		key, val := itr.Current()
194		got[string(key)] = val
195		err = itr.Next()
196	}
197	if err != ErrIteratorDone {
198		t.Errorf("iterator error: %v", err)
199	}
200
201	for i := 0; i < len(dataset); i++ {
202		foundVal, ok := got[dataset[i]]
203		if !ok {
204			t.Fatalf("expected to find key, but didn't: %s", dataset[i])
205		}
206
207		if foundVal != randomThousandVals[i] {
208			t.Fatalf("expected value %d for key %s, but got %d", randomThousandVals[i], dataset[i], foundVal)
209		}
210
211		// now remove it
212		delete(got, dataset[i])
213	}
214
215	if len(got) != 0 {
216		t.Fatalf("expected got map to be empty after checking, still has %v", got)
217	}
218}
219
220func TestRoundTripEmpty(t *testing.T) {
221	f, err := ioutil.TempFile("", "vellum")
222	if err != nil {
223		t.Fatal(err)
224	}
225	defer func() {
226		err = f.Close()
227		if err != nil {
228			t.Fatal(err)
229		}
230	}()
231	defer func() {
232		err = os.Remove(f.Name())
233		if err != nil {
234			t.Fatal(err)
235		}
236	}()
237
238	b, err := New(f, nil)
239	if err != nil {
240		t.Fatalf("error creating builder: %v", err)
241	}
242
243	err = b.Close()
244	if err != nil {
245		t.Fatalf("error closing: %v", err)
246	}
247
248	fst, err := Open(f.Name())
249	if err != nil {
250		t.Fatalf("error loading set: %v", err)
251	}
252	defer func() {
253		err = fst.Close()
254		if err != nil {
255			t.Fatal(err)
256		}
257	}()
258
259	if fst.Len() != 0 {
260		t.Fatalf("expected length 0, got %d", fst.Len())
261	}
262
263	// first check all the expected values
264	got := map[string]uint64{}
265	itr, err := fst.Iterator(nil, nil)
266	for err == nil {
267		key, val := itr.Current()
268		got[string(key)] = val
269		err = itr.Next()
270	}
271	if err != ErrIteratorDone {
272		t.Errorf("iterator error: %v", err)
273	}
274	if len(got) > 0 {
275		t.Errorf("expected not to see anything, got %v", got)
276	}
277}
278
279func TestRoundTripEmptyString(t *testing.T) {
280	f, err := ioutil.TempFile("", "vellum")
281	if err != nil {
282		t.Fatal(err)
283	}
284	defer func() {
285		err = f.Close()
286		if err != nil {
287			t.Fatal(err)
288		}
289	}()
290	defer func() {
291		err = os.Remove(f.Name())
292		if err != nil {
293			t.Fatal(err)
294		}
295	}()
296
297	b, err := New(f, nil)
298	if err != nil {
299		t.Fatalf("error creating builder: %v", err)
300	}
301
302	err = b.Insert([]byte(""), 1)
303	if err != nil {
304		t.Fatalf("error inserting empty string")
305	}
306
307	err = b.Close()
308	if err != nil {
309		t.Fatalf("error closing: %v", err)
310	}
311
312	fst, err := Open(f.Name())
313	if err != nil {
314		t.Fatalf("error loading set: %v", err)
315	}
316	defer func() {
317		err = fst.Close()
318		if err != nil {
319			t.Fatal(err)
320		}
321	}()
322
323	if fst.Len() != 1 {
324		t.Fatalf("expected length 1, got %d", fst.Len())
325	}
326
327	// first check all the expected values
328	want := map[string]uint64{
329		"": 1,
330	}
331	got := map[string]uint64{}
332	itr, err := fst.Iterator(nil, nil)
333	for err == nil {
334		key, val := itr.Current()
335		got[string(key)] = val
336		err = itr.Next()
337	}
338	if err != ErrIteratorDone {
339		t.Errorf("iterator error: %v", err)
340	}
341	if !reflect.DeepEqual(want, got) {
342		t.Errorf("expected %v, got: %v", want, got)
343	}
344}
345
346func TestRoundTripEmptyStringAndOthers(t *testing.T) {
347	f, err := ioutil.TempFile("", "vellum")
348	if err != nil {
349		t.Fatal(err)
350	}
351	defer func() {
352		err = f.Close()
353		if err != nil {
354			t.Fatal(err)
355		}
356	}()
357	defer func() {
358		err = os.Remove(f.Name())
359		if err != nil {
360			t.Fatal(err)
361		}
362	}()
363
364	b, err := New(f, nil)
365	if err != nil {
366		t.Fatalf("error creating builder: %v", err)
367	}
368
369	err = b.Insert([]byte(""), 0)
370	if err != nil {
371		t.Fatalf("error inserting empty string")
372	}
373	err = b.Insert([]byte("a"), 0)
374	if err != nil {
375		t.Fatalf("error inserting empty string")
376	}
377
378	err = b.Close()
379	if err != nil {
380		t.Fatalf("error closing: %v", err)
381	}
382
383	fst, err := Open(f.Name())
384	if err != nil {
385		t.Fatalf("error loading set: %v", err)
386	}
387	defer func() {
388		err = fst.Close()
389		if err != nil {
390			t.Fatal(err)
391		}
392	}()
393
394	if fst.Len() != 2 {
395		t.Fatalf("expected length 2, got %d", fst.Len())
396	}
397
398	// first check all the expected values
399	want := map[string]uint64{
400		"":  0,
401		"a": 0,
402	}
403	got := map[string]uint64{}
404	itr, err := fst.Iterator(nil, nil)
405	for err == nil {
406		key, val := itr.Current()
407		got[string(key)] = val
408		err = itr.Next()
409	}
410	if err != ErrIteratorDone {
411		t.Errorf("iterator error: %v", err)
412	}
413	if !reflect.DeepEqual(want, got) {
414		t.Errorf("expected %v, got: %v", want, got)
415	}
416}
417
418func TestMerge(t *testing.T) {
419
420	// first create a file with the smallSample data
421	f, err := ioutil.TempFile("", "vellum1")
422	if err != nil {
423		t.Fatal(err)
424	}
425	defer func() {
426		err = f.Close()
427		if err != nil {
428			t.Fatal(err)
429		}
430	}()
431	defer func() {
432		err = os.Remove(f.Name())
433		if err != nil {
434			t.Fatal(err)
435		}
436	}()
437
438	b, err := New(f, nil)
439	if err != nil {
440		t.Fatalf("error creating builder: %v", err)
441	}
442
443	err = insertStringMap(b, smallSample)
444	if err != nil {
445		t.Fatalf("error building: %v", err)
446	}
447
448	err = b.Close()
449	if err != nil {
450		t.Fatalf("err closing: %v", err)
451	}
452
453	smallSample2 := map[string]uint64{
454		"bold": 25,
455		"last": 1,
456		"next": 500,
457		"tank": 0,
458	}
459
460	// next create a file with the smallSample2 data
461	f2, err := ioutil.TempFile("", "vellum1")
462	if err != nil {
463		t.Fatal(err)
464	}
465	defer func() {
466		err = f2.Close()
467		if err != nil {
468			t.Fatal(err)
469		}
470	}()
471	defer func() {
472		err = os.Remove(f2.Name())
473		if err != nil {
474			t.Fatal(err)
475		}
476	}()
477
478	b, err = New(f2, nil)
479	if err != nil {
480		t.Fatalf("error creating builder: %v", err)
481	}
482
483	err = insertStringMap(b, smallSample2)
484	if err != nil {
485		t.Fatalf("error building: %v", err)
486	}
487
488	err = b.Close()
489	if err != nil {
490		t.Fatalf("err closing: %v", err)
491	}
492
493	// now open them both up
494	fst, err := Open(f.Name())
495	if err != nil {
496		t.Fatalf("error loading set: %v", err)
497	}
498	defer func() {
499		err = fst.Close()
500		if err != nil {
501			t.Fatal(err)
502		}
503	}()
504	fst2, err := Open(f2.Name())
505	if err != nil {
506		t.Fatalf("error loading set: %v", err)
507	}
508	defer func() {
509		err = fst2.Close()
510		if err != nil {
511			t.Fatal(err)
512		}
513	}()
514
515	// create full range iterators on both
516	itr, err := fst.Iterator(nil, nil)
517	if err != nil {
518		t.Fatalf("error opening iterator: %v", err)
519	}
520	itr2, err := fst2.Iterator(nil, nil)
521	if err != nil {
522		t.Fatalf("error opening iterator: %v", err)
523	}
524
525	f3, err := ioutil.TempFile("", "vellum1")
526	if err != nil {
527		t.Fatal(err)
528	}
529	defer func() {
530		err = f3.Close()
531		if err != nil {
532			t.Fatal(err)
533		}
534	}()
535	defer func() {
536		err = os.Remove(f3.Name())
537		if err != nil {
538			t.Fatal(err)
539		}
540	}()
541
542	err = Merge(f3, nil, []Iterator{itr, itr2}, MergeSum)
543	if err != nil {
544		t.Fatalf("error merging iterators: %v", err)
545	}
546
547	// now check it
548	fstc, err := Open(f3.Name())
549	if err != nil {
550		t.Fatalf("error loading set: %v", err)
551	}
552	defer func() {
553		err = fstc.Close()
554		if err != nil {
555			t.Fatal(err)
556		}
557	}()
558
559	if fstc.Len() != 8 {
560		t.Fatalf("expected length 8, got %d", fst.Len())
561	}
562
563	// now check all the expected values
564	want := map[string]uint64{
565		"mon":   2,
566		"tues":  3,
567		"thurs": 5,
568		"tye":   99,
569		"bold":  25,
570		"last":  1,
571		"next":  500,
572		"tank":  0,
573	}
574	got := map[string]uint64{}
575	itrc, err := fstc.Iterator(nil, nil)
576	for err == nil {
577		key, val := itrc.Current()
578		got[string(key)] = val
579		err = itrc.Next()
580	}
581	if err != ErrIteratorDone {
582		t.Errorf("iterator error: %v", err)
583	}
584	if !reflect.DeepEqual(want, got) {
585		t.Errorf("expected %v, got: %v", want, got)
586	}
587}
588
589func BenchmarkKey4000K(b *testing.B) {
590	benchmarkBigKey(b, 4000000)
591}
592
593func BenchmarkKey1000K(b *testing.B) {
594	benchmarkBigKey(b, 1000000)
595}
596
597func BenchmarkKey100K(b *testing.B) {
598	benchmarkBigKey(b, 100000)
599}
600
601func BenchmarkKey10K(b *testing.B) {
602	benchmarkBigKey(b, 10000)
603}
604
605func BenchmarkKey1K(b *testing.B) {
606	benchmarkBigKey(b, 1000)
607}
608
609func benchmarkBigKey(b *testing.B, n int) {
610	big := bytes.Repeat([]byte("a"), n)
611
612	b.ResetTimer()
613
614	for i := 0; i < b.N; i++ {
615		b, err := New(ioutil.Discard, nil)
616		if err != nil {
617			break
618		}
619
620		err = b.Insert(big, 0)
621		if err != nil {
622			break
623		}
624
625		err = b.Close()
626		if err != nil {
627			break
628		}
629	}
630}
631