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