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	minKey, _ := fst.GetMinKey()
143	if string(minKey) != "mon" {
144		t.Errorf("expected minKey 'mon', got %v", string(minKey))
145	}
146
147	maxKey, _ := fst.GetMaxKey()
148	if string(maxKey) != "tye" {
149		t.Errorf("expected maxKey 'tye', got %v", string(maxKey))
150	}
151}
152
153func TestRoundTripThousand(t *testing.T) {
154	dataset := thousandTestWords
155	randomThousandVals := randomValues(dataset)
156
157	f, err := ioutil.TempFile("", "vellum")
158	if err != nil {
159		t.Fatal(err)
160	}
161	defer func() {
162		err = f.Close()
163		if err != nil {
164			t.Fatal(err)
165		}
166	}()
167	defer func() {
168		err = os.Remove(f.Name())
169		if err != nil {
170			t.Fatal(err)
171		}
172	}()
173
174	b, err := New(f, nil)
175	if err != nil {
176		t.Fatalf("error creating builder: %v", err)
177	}
178
179	err = insertStrings(b, dataset, randomThousandVals)
180	if err != nil {
181		t.Fatalf("error inserting thousand words: %v", err)
182	}
183	err = b.Close()
184	if err != nil {
185		t.Fatalf("error closing builder: %v", err)
186	}
187
188	fst, err := Open(f.Name())
189	if err != nil {
190		t.Fatalf("error loading set: %v", err)
191	}
192	defer func() {
193		err = fst.Close()
194		if err != nil {
195			t.Fatal(err)
196		}
197	}()
198
199	// first check all the expected values
200	got := map[string]uint64{}
201	itr, err := fst.Iterator(nil, nil)
202	for err == nil {
203		key, val := itr.Current()
204		got[string(key)] = val
205		err = itr.Next()
206	}
207	if err != ErrIteratorDone {
208		t.Errorf("iterator error: %v", err)
209	}
210
211	for i := 0; i < len(dataset); i++ {
212		foundVal, ok := got[dataset[i]]
213		if !ok {
214			t.Fatalf("expected to find key, but didn't: %s", dataset[i])
215		}
216
217		if foundVal != randomThousandVals[i] {
218			t.Fatalf("expected value %d for key %s, but got %d", randomThousandVals[i], dataset[i], foundVal)
219		}
220
221		// now remove it
222		delete(got, dataset[i])
223	}
224
225	if len(got) != 0 {
226		t.Fatalf("expected got map to be empty after checking, still has %v", got)
227	}
228}
229
230func TestRoundTripEmpty(t *testing.T) {
231	f, err := ioutil.TempFile("", "vellum")
232	if err != nil {
233		t.Fatal(err)
234	}
235	defer func() {
236		err = f.Close()
237		if err != nil {
238			t.Fatal(err)
239		}
240	}()
241	defer func() {
242		err = os.Remove(f.Name())
243		if err != nil {
244			t.Fatal(err)
245		}
246	}()
247
248	b, err := New(f, nil)
249	if err != nil {
250		t.Fatalf("error creating builder: %v", err)
251	}
252
253	err = b.Close()
254	if err != nil {
255		t.Fatalf("error closing: %v", err)
256	}
257
258	fst, err := Open(f.Name())
259	if err != nil {
260		t.Fatalf("error loading set: %v", err)
261	}
262	defer func() {
263		err = fst.Close()
264		if err != nil {
265			t.Fatal(err)
266		}
267	}()
268
269	if fst.Len() != 0 {
270		t.Fatalf("expected length 0, got %d", fst.Len())
271	}
272
273	// first check all the expected values
274	got := map[string]uint64{}
275	itr, err := fst.Iterator(nil, nil)
276	for err == nil {
277		key, val := itr.Current()
278		got[string(key)] = val
279		err = itr.Next()
280	}
281	if err != ErrIteratorDone {
282		t.Errorf("iterator error: %v", err)
283	}
284	if len(got) > 0 {
285		t.Errorf("expected not to see anything, got %v", got)
286	}
287}
288
289func TestRoundTripEmptyString(t *testing.T) {
290	f, err := ioutil.TempFile("", "vellum")
291	if err != nil {
292		t.Fatal(err)
293	}
294	defer func() {
295		err = f.Close()
296		if err != nil {
297			t.Fatal(err)
298		}
299	}()
300	defer func() {
301		err = os.Remove(f.Name())
302		if err != nil {
303			t.Fatal(err)
304		}
305	}()
306
307	b, err := New(f, nil)
308	if err != nil {
309		t.Fatalf("error creating builder: %v", err)
310	}
311
312	err = b.Insert([]byte(""), 1)
313	if err != nil {
314		t.Fatalf("error inserting empty string")
315	}
316
317	err = b.Close()
318	if err != nil {
319		t.Fatalf("error closing: %v", err)
320	}
321
322	fst, err := Open(f.Name())
323	if err != nil {
324		t.Fatalf("error loading set: %v", err)
325	}
326	defer func() {
327		err = fst.Close()
328		if err != nil {
329			t.Fatal(err)
330		}
331	}()
332
333	if fst.Len() != 1 {
334		t.Fatalf("expected length 1, got %d", fst.Len())
335	}
336
337	// first check all the expected values
338	want := map[string]uint64{
339		"": 1,
340	}
341	got := map[string]uint64{}
342	itr, err := fst.Iterator(nil, nil)
343	for err == nil {
344		key, val := itr.Current()
345		got[string(key)] = val
346		err = itr.Next()
347	}
348	if err != ErrIteratorDone {
349		t.Errorf("iterator error: %v", err)
350	}
351	if !reflect.DeepEqual(want, got) {
352		t.Errorf("expected %v, got: %v", want, got)
353	}
354}
355
356func TestRoundTripEmptyStringAndOthers(t *testing.T) {
357	f, err := ioutil.TempFile("", "vellum")
358	if err != nil {
359		t.Fatal(err)
360	}
361	defer func() {
362		err = f.Close()
363		if err != nil {
364			t.Fatal(err)
365		}
366	}()
367	defer func() {
368		err = os.Remove(f.Name())
369		if err != nil {
370			t.Fatal(err)
371		}
372	}()
373
374	b, err := New(f, nil)
375	if err != nil {
376		t.Fatalf("error creating builder: %v", err)
377	}
378
379	err = b.Insert([]byte(""), 0)
380	if err != nil {
381		t.Fatalf("error inserting empty string")
382	}
383	err = b.Insert([]byte("a"), 0)
384	if err != nil {
385		t.Fatalf("error inserting empty string")
386	}
387
388	err = b.Close()
389	if err != nil {
390		t.Fatalf("error closing: %v", err)
391	}
392
393	fst, err := Open(f.Name())
394	if err != nil {
395		t.Fatalf("error loading set: %v", err)
396	}
397	defer func() {
398		err = fst.Close()
399		if err != nil {
400			t.Fatal(err)
401		}
402	}()
403
404	if fst.Len() != 2 {
405		t.Fatalf("expected length 2, got %d", fst.Len())
406	}
407
408	// first check all the expected values
409	want := map[string]uint64{
410		"":  0,
411		"a": 0,
412	}
413	got := map[string]uint64{}
414	itr, err := fst.Iterator(nil, nil)
415	for err == nil {
416		key, val := itr.Current()
417		got[string(key)] = val
418		err = itr.Next()
419	}
420	if err != ErrIteratorDone {
421		t.Errorf("iterator error: %v", err)
422	}
423	if !reflect.DeepEqual(want, got) {
424		t.Errorf("expected %v, got: %v", want, got)
425	}
426}
427
428func TestMerge(t *testing.T) {
429
430	// first create a file with the smallSample data
431	f, err := ioutil.TempFile("", "vellum1")
432	if err != nil {
433		t.Fatal(err)
434	}
435	defer func() {
436		err = f.Close()
437		if err != nil {
438			t.Fatal(err)
439		}
440	}()
441	defer func() {
442		err = os.Remove(f.Name())
443		if err != nil {
444			t.Fatal(err)
445		}
446	}()
447
448	b, err := New(f, nil)
449	if err != nil {
450		t.Fatalf("error creating builder: %v", err)
451	}
452
453	err = insertStringMap(b, smallSample)
454	if err != nil {
455		t.Fatalf("error building: %v", err)
456	}
457
458	err = b.Close()
459	if err != nil {
460		t.Fatalf("err closing: %v", err)
461	}
462
463	smallSample2 := map[string]uint64{
464		"bold": 25,
465		"last": 1,
466		"next": 500,
467		"tank": 0,
468	}
469
470	// next create a file with the smallSample2 data
471	f2, err := ioutil.TempFile("", "vellum1")
472	if err != nil {
473		t.Fatal(err)
474	}
475	defer func() {
476		err = f2.Close()
477		if err != nil {
478			t.Fatal(err)
479		}
480	}()
481	defer func() {
482		err = os.Remove(f2.Name())
483		if err != nil {
484			t.Fatal(err)
485		}
486	}()
487
488	b, err = New(f2, nil)
489	if err != nil {
490		t.Fatalf("error creating builder: %v", err)
491	}
492
493	err = insertStringMap(b, smallSample2)
494	if err != nil {
495		t.Fatalf("error building: %v", err)
496	}
497
498	err = b.Close()
499	if err != nil {
500		t.Fatalf("err closing: %v", err)
501	}
502
503	// now open them both up
504	fst, err := Open(f.Name())
505	if err != nil {
506		t.Fatalf("error loading set: %v", err)
507	}
508	defer func() {
509		err = fst.Close()
510		if err != nil {
511			t.Fatal(err)
512		}
513	}()
514	fst2, err := Open(f2.Name())
515	if err != nil {
516		t.Fatalf("error loading set: %v", err)
517	}
518	defer func() {
519		err = fst2.Close()
520		if err != nil {
521			t.Fatal(err)
522		}
523	}()
524
525	// create full range iterators on both
526	itr, err := fst.Iterator(nil, nil)
527	if err != nil {
528		t.Fatalf("error opening iterator: %v", err)
529	}
530	itr2, err := fst2.Iterator(nil, nil)
531	if err != nil {
532		t.Fatalf("error opening iterator: %v", err)
533	}
534
535	f3, err := ioutil.TempFile("", "vellum1")
536	if err != nil {
537		t.Fatal(err)
538	}
539	defer func() {
540		err = f3.Close()
541		if err != nil {
542			t.Fatal(err)
543		}
544	}()
545	defer func() {
546		err = os.Remove(f3.Name())
547		if err != nil {
548			t.Fatal(err)
549		}
550	}()
551
552	err = Merge(f3, nil, []Iterator{itr, itr2}, MergeSum)
553	if err != nil {
554		t.Fatalf("error merging iterators: %v", err)
555	}
556
557	// now check it
558	fstc, err := Open(f3.Name())
559	if err != nil {
560		t.Fatalf("error loading set: %v", err)
561	}
562	defer func() {
563		err = fstc.Close()
564		if err != nil {
565			t.Fatal(err)
566		}
567	}()
568
569	if fstc.Len() != 8 {
570		t.Fatalf("expected length 8, got %d", fst.Len())
571	}
572
573	// now check all the expected values
574	want := map[string]uint64{
575		"mon":   2,
576		"tues":  3,
577		"thurs": 5,
578		"tye":   99,
579		"bold":  25,
580		"last":  1,
581		"next":  500,
582		"tank":  0,
583	}
584	got := map[string]uint64{}
585	itrc, err := fstc.Iterator(nil, nil)
586	for err == nil {
587		key, val := itrc.Current()
588		got[string(key)] = val
589		err = itrc.Next()
590	}
591	if err != ErrIteratorDone {
592		t.Errorf("iterator error: %v", err)
593	}
594	if !reflect.DeepEqual(want, got) {
595		t.Errorf("expected %v, got: %v", want, got)
596	}
597}
598
599func BenchmarkKey4000K(b *testing.B) {
600	benchmarkBigKey(b, 4000000)
601}
602
603func BenchmarkKey1000K(b *testing.B) {
604	benchmarkBigKey(b, 1000000)
605}
606
607func BenchmarkKey100K(b *testing.B) {
608	benchmarkBigKey(b, 100000)
609}
610
611func BenchmarkKey10K(b *testing.B) {
612	benchmarkBigKey(b, 10000)
613}
614
615func BenchmarkKey1K(b *testing.B) {
616	benchmarkBigKey(b, 1000)
617}
618
619func benchmarkBigKey(b *testing.B, n int) {
620	big := bytes.Repeat([]byte("a"), n)
621
622	b.ResetTimer()
623
624	for i := 0; i < b.N; i++ {
625		b, err := New(ioutil.Discard, nil)
626		if err != nil {
627			break
628		}
629
630		err = b.Insert(big, 0)
631		if err != nil {
632			break
633		}
634
635		err = b.Close()
636		if err != nil {
637			break
638		}
639	}
640}
641
642func TestMaxWithSubstring(t *testing.T) {
643	var buf bytes.Buffer
644	builder, err := New(&buf, nil)
645	if err != nil {
646		t.Fatal(err)
647	}
648
649	err = builder.Insert([]byte("1"), 1)
650	if err != nil {
651		t.Fatal(err)
652	}
653
654	err = builder.Insert([]byte("11"), 1)
655	if err != nil {
656		t.Fatal(err)
657	}
658
659	err = builder.Insert([]byte("9"), 9)
660	if err != nil {
661		t.Fatal(err)
662	}
663
664	err = builder.Insert([]byte("99"), 99)
665	if err != nil {
666		t.Fatal(err)
667	}
668
669	err = builder.Close()
670	if err != nil {
671		t.Fatal(err)
672	}
673
674	fst, err := Load(buf.Bytes())
675	if err != nil {
676		t.Fatal(err)
677	}
678
679	mink, err := fst.GetMinKey()
680	if err != nil {
681		t.Fatal(err)
682	}
683
684	if string(mink) != "1" {
685		t.Fatalf("expected max key 1, got %s", string(mink))
686	}
687
688	maxk, err := fst.GetMaxKey()
689	if err != nil {
690		t.Fatal(err)
691	}
692
693	if string(maxk) != "99" {
694		t.Fatalf("expected max key 99, got %s", string(maxk))
695	}
696}
697