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	"bufio"
19	"io/ioutil"
20	"math/rand"
21	"os"
22	"sort"
23	"testing"
24)
25
26func init() {
27	thousandTestWords, _ = loadWords("data/words-1000.txt")
28}
29
30// this simple test case only has a shared final state
31// it also tests out of order insert
32func TestBuilderSimple(t *testing.T) {
33	b, err := New(ioutil.Discard, nil)
34	if err != nil {
35		t.Fatalf("error creating builder: %v", err)
36	}
37
38	// add our first string
39	err = b.Insert([]byte("jul"), 0)
40	if err != nil {
41		t.Errorf("got error inserting string: %v", err)
42	}
43	// expect len to be 1
44	if b.len != 1 {
45		t.Errorf("expected node count to be 1, got %v", b.len)
46	}
47
48	// try to add a value out of order (not allowed)
49	err = b.Insert([]byte("abc"), 0)
50	if err == nil {
51		t.Errorf("expected err, got nil")
52	}
53
54	// add a second string
55	err = b.Insert([]byte("mar"), 0)
56	if err != nil {
57		t.Errorf("got error inserting string: %v", err)
58	}
59	// expect len to grow by 1
60	if b.len != 2 {
61		t.Errorf("expected node count to be 2, got %v", b.len)
62	}
63
64	// now close the builder
65	err = b.Close()
66	if err != nil {
67		t.Errorf("got error closing set builder: %v", err)
68	}
69}
70
71func TestBuilderSharedPrefix(t *testing.T) {
72	b, err := New(ioutil.Discard, nil)
73	if err != nil {
74		t.Fatalf("error creating builder: %v", err)
75	}
76
77	// add our first string
78	err = b.Insert([]byte("car"), 0)
79	if err != nil {
80		t.Errorf("got error inserting string: %v", err)
81	}
82	// expect len to be 1
83	if b.len != 1 {
84		t.Errorf("expected node count to be 1, got %v", b.len)
85	}
86
87	// add a second string
88	err = b.Insert([]byte("cat"), 0)
89	if err != nil {
90		t.Errorf("got error inserting string: %v", err)
91	}
92	// expect len to be 2
93	if b.len != 2 {
94		t.Errorf("expected node count to be 2, got %v", b.len)
95	}
96
97	// now close the builder
98	err = b.Close()
99	if err != nil {
100		t.Errorf("got error closing set builder: %v", err)
101	}
102}
103
104func randomValues(list []string) []uint64 {
105	rv := make([]uint64, len(list))
106	for i := range list {
107		rv[i] = uint64(rand.Uint64())
108	}
109	return rv
110}
111
112func insertStrings(b *Builder, list []string, vals []uint64) error {
113	for i, item := range list {
114		err := b.Insert([]byte(item), vals[i])
115		if err != nil {
116			return err
117		}
118	}
119	return nil
120}
121
122var smallSample = map[string]uint64{
123	"mon":   2,
124	"tues":  3,
125	"thurs": 5,
126	"tye":   99,
127}
128
129func insertStringMap(b *Builder, m map[string]uint64) error {
130	// make list of keys
131	keys := make([]string, 0, len(m))
132	for k := range m {
133		keys = append(keys, k)
134	}
135	// sort it
136	sort.Strings(keys)
137	// insert in sorted order
138	for _, k := range keys {
139		err := b.Insert([]byte(k), m[k])
140		if err != nil {
141			return err
142		}
143	}
144	return nil
145}
146
147func TestBuilderNodeEquiv(t *testing.T) {
148	tests := []struct {
149		desc string
150		a    *builderNode
151		b    *builderNode
152		want bool
153	}{
154		{
155			"both states final",
156			&builderNode{
157				final: true,
158			},
159			&builderNode{
160				final: true,
161			},
162			true,
163		},
164		{
165			"both states final, different final val",
166			&builderNode{
167				final:       true,
168				finalOutput: 7,
169			},
170			&builderNode{
171				final:       true,
172				finalOutput: 9,
173			},
174			false,
175		},
176		{
177			"both states final, same transitions, but different trans val",
178			&builderNode{
179				final: true,
180				trans: []transition{
181					{in: 'a', out: 7},
182				},
183			},
184			&builderNode{
185				final: true,
186				trans: []transition{
187					{in: 'a', out: 9},
188				},
189			},
190			false,
191		},
192	}
193
194	for _, test := range tests {
195		t.Run(test.desc, func(t *testing.T) {
196			got := test.a.equiv(test.b)
197			if got != test.want {
198				t.Errorf("wanted: %t, got: %t", test.want, got)
199			}
200		})
201	}
202}
203
204func loadWords(path string) ([]string, error) {
205	var rv []string
206
207	file, err := os.Open(path)
208	if err != nil {
209		return nil, err
210	}
211
212	scanner := bufio.NewScanner(file)
213	for scanner.Scan() {
214		word := append([]byte(nil), scanner.Bytes()...)
215		rv = append(rv, string(word))
216		if err != nil {
217			return nil, err
218		}
219	}
220
221	if err = scanner.Err(); err != nil {
222		return nil, err
223	}
224
225	err = file.Close()
226	if err != nil {
227		return nil, err
228	}
229
230	return rv, nil
231}
232
233var thousandTestWords []string
234
235func BenchmarkBuilder(b *testing.B) {
236	dataset := thousandTestWords
237	randomThousandVals := randomValues(dataset)
238
239	b.ResetTimer()
240
241	for i := 0; i < b.N; i++ {
242
243		builder, err := New(ioutil.Discard, nil)
244		if err != nil {
245			b.Fatalf("error creating builder: %v", err)
246		}
247		err = insertStrings(builder, dataset, randomThousandVals)
248		if err != nil {
249			b.Fatalf("error inserting thousand words: %v", err)
250		}
251		err = builder.Close()
252		if err != nil {
253			b.Fatalf("error closing builder: %v", err)
254		}
255	}
256}
257