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 "reflect" 19 "testing" 20) 21 22func TestDecoderVersionError(t *testing.T) { 23 _, err := loadDecoder(629, nil) 24 if err == nil { 25 t.Errorf("expected error loading decoder version 629, got nil") 26 } 27} 28 29func TestShortHeader(t *testing.T) { 30 header := make([]byte, 15) 31 _, _, err := decodeHeader(header) 32 if err == nil { 33 t.Errorf("expected error decoding short header, got nil") 34 } 35} 36 37func TestDecoderRootLen(t *testing.T) { 38 d := newDecoderV1([]byte{1, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0}) 39 if d.getLen() != 1 { 40 t.Fatalf("expected parsed footer length 1, got %d", d.getLen()) 41 } 42 if d.getRoot() != 2 { 43 t.Fatalf("expected parsed footer length 2, got %d", d.getLen()) 44 } 45} 46 47func TestDecoderStateAt(t *testing.T) { 48 tests := []struct { 49 desc string 50 data []byte 51 want *fstStateV1 52 }{ 53 { 54 "one trans, trans next, common char", 55 []byte{ 56 // header 57 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 58 // test node data 59 oneTransition | transitionNext | encodeCommon('a'), 60 // footer 61 1, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 62 }, 63 &fstStateV1{ 64 numTrans: 1, 65 top: 16, 66 bottom: 16, 67 singleTransChar: 'a', 68 singleTransNext: true, 69 singleTransAddr: 15, 70 }, 71 }, 72 { 73 "one trans, trans next, uncommon char", 74 []byte{ 75 // header 76 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 77 // test node data 78 0xff, 79 oneTransition | transitionNext, 80 // footer 81 1, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 82 }, 83 &fstStateV1{ 84 numTrans: 1, 85 top: 17, 86 bottom: 16, 87 singleTransChar: 0xff, 88 singleTransNext: true, 89 singleTransAddr: 15, 90 }, 91 }, 92 { 93 "one trans, trans not next, common char", 94 []byte{ 95 // header 96 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 97 // test node data 98 4, // delta address packed 99 1<<4 | 0, // pack sizes 100 oneTransition | encodeCommon('a'), 101 // footer 102 1, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 103 }, 104 &fstStateV1{ 105 numTrans: 1, 106 top: 18, 107 bottom: 16, 108 singleTransChar: 'a', 109 singleTransNext: false, 110 singleTransAddr: 12, 111 transSize: 1, 112 }, 113 }, 114 { 115 "one trans, trans not next, uncommon char", 116 []byte{ 117 // header 118 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 119 // test node data 120 4, // delta address packed 121 1<<4 | 0, // pack sizes 122 0xff, 123 oneTransition, 124 // footer 125 1, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 126 }, 127 &fstStateV1{ 128 numTrans: 1, 129 top: 19, 130 bottom: 16, 131 singleTransChar: 0xff, 132 singleTransNext: false, 133 singleTransAddr: 12, 134 transSize: 1, 135 }, 136 }, 137 { 138 "one trans, trans not next, common char, with value", 139 []byte{ 140 // header 141 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 142 // test node data 143 27, // trans value 144 4, // delta address packed 145 1<<4 | 1, // pack sizes 146 oneTransition | encodeCommon('a'), 147 // footer 148 1, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 149 }, 150 &fstStateV1{ 151 numTrans: 1, 152 top: 19, 153 bottom: 16, 154 singleTransChar: 'a', 155 singleTransNext: false, 156 singleTransAddr: 12, 157 singleTransOut: 27, 158 transSize: 1, 159 outSize: 1, 160 }, 161 }, 162 { 163 "one trans, trans not next, uncommon char, with value", 164 []byte{ 165 // header 166 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 167 // test node data 168 39, // trans val 169 4, // delta address packed 170 1<<4 | 1, // pack sizes 171 0xff, 172 oneTransition, 173 // footer 174 1, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 175 }, 176 &fstStateV1{ 177 numTrans: 1, 178 top: 20, 179 bottom: 16, 180 singleTransChar: 0xff, 181 singleTransNext: false, 182 singleTransAddr: 12, 183 singleTransOut: 39, 184 transSize: 1, 185 outSize: 1, 186 }, 187 }, 188 { 189 "many trans, not final, no values", 190 []byte{ 191 // header 192 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 193 // test node data 194 2, // delta addresses packed 195 3, 196 4, 197 'c', // encoded keys reversed 198 'b', 199 'a', 200 1<<4 | 0, // pack sizes 201 encodeNumTrans(3), 202 // footer 203 1, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 204 }, 205 &fstStateV1{ 206 numTrans: 3, 207 top: 23, 208 bottom: 16, 209 transSize: 1, 210 destBottom: 16, 211 destTop: 19, 212 transBottom: 19, 213 transTop: 22, 214 }, 215 }, 216 { 217 "many trans, not final, with values", 218 []byte{ 219 // header 220 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 221 // test node data 222 7, // values reversed 223 0, 224 3, 225 2, // delta addresses reversed 226 3, 227 4, 228 'c', // encoded keys reversed 229 'b', 230 'a', 231 1<<4 | 1, // pack sizes 232 encodeNumTrans(3), 233 // footer 234 1, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 235 }, 236 &fstStateV1{ 237 numTrans: 3, 238 top: 26, 239 bottom: 16, 240 transSize: 1, 241 outSize: 1, 242 outBottom: 16, 243 outTop: 19, 244 destBottom: 19, 245 destTop: 22, 246 transBottom: 22, 247 transTop: 25, 248 }, 249 }, 250 { 251 "many trans, final, with values", 252 []byte{ 253 // header 254 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 255 // test node data 256 9, // node final val 257 7, // values reversed 258 0, 259 3, 260 2, // delta addresses reversed 261 3, 262 4, 263 'c', // encoded keys reversed 264 'b', 265 'a', 266 1<<4 | 1, // pack sizes 267 stateFinal | encodeNumTrans(3), 268 // footer 269 1, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 270 }, 271 &fstStateV1{ 272 final: true, 273 numTrans: 3, 274 top: 27, 275 bottom: 16, 276 transSize: 1, 277 outSize: 1, 278 outBottom: 17, 279 outTop: 20, 280 destBottom: 20, 281 destTop: 23, 282 transBottom: 23, 283 transTop: 26, 284 outFinal: 16, 285 }, 286 }, 287 { 288 "max trans, ", 289 []byte{ 290 // header 291 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 292 // test node data 293 // delta addresses packed 294 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 295 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 296 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 297 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 298 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 299 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 300 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 301 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 302 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 303 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 304 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 305 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 306 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 307 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 308 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 309 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 0x4, 310 // encoded keys reversed 311 0x0, 0x1, 0x2, 0x3, 0x4, 0x5, 0x6, 0x7, 0x8, 0x9, 0xa, 0xb, 0xc, 0xd, 0xe, 0xf, 312 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 313 0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f, 314 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f, 315 0x40, 0x41, 0x42, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48, 0x49, 0x4a, 0x4b, 0x4c, 0x4d, 0x4e, 0x4f, 316 0x50, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x57, 0x58, 0x59, 0x5a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f, 317 0x60, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f, 318 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 319 0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87, 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f, 320 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98, 0x99, 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f, 321 0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7, 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf, 322 0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7, 0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf, 323 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7, 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf, 324 0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7, 0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf, 325 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7, 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef, 326 0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff, 327 1<<4 | 0, // pack sizes 328 1, // actual trans 1 == 256 329 0, // zero trans (wont fit) 330 // footer 331 1, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 332 }, 333 &fstStateV1{ 334 numTrans: 256, 335 top: 530, 336 bottom: 16, 337 transSize: 1, 338 destBottom: 16, 339 destTop: 272, 340 transBottom: 272, 341 transTop: 528, 342 }, 343 }, 344 } 345 346 for _, test := range tests { 347 t.Run(test.desc, func(t *testing.T) { 348 d := newDecoderV1(test.data) 349 test.want.data = test.data 350 got, err := d.stateAt(len(test.data)-17, nil) 351 if err != nil { 352 t.Fatal(err) 353 } 354 if !reflect.DeepEqual(got, test.want) { 355 t.Errorf("wanted: %+v, got: %+v", test.want, got) 356 } 357 addr := got.Address() 358 if addr != test.want.top { 359 t.Errorf("expected address to match: %d - %d", addr, test.want.top) 360 } 361 fin := got.Final() 362 if fin != test.want.final { 363 t.Errorf("expected final to match: %t - %t", fin, test.want.final) 364 } 365 ntrans := got.NumTransitions() 366 if ntrans != test.want.numTrans { 367 t.Errorf("expected num trans to match: %d - %d", ntrans, test.want.numTrans) 368 } 369 }) 370 } 371} 372 373func TestFSTStateFinalOutput(t *testing.T) { 374 tests := []struct { 375 desc string 376 in *fstStateV1 377 want uint64 378 }{ 379 { 380 "final output for final state", 381 &fstStateV1{ 382 data: []byte{7}, 383 numTrans: 2, 384 final: true, 385 outSize: 1, 386 outFinal: 0, 387 }, 388 7, 389 }, 390 { 391 "final output for non-final state", 392 &fstStateV1{ 393 data: []byte{7}, 394 numTrans: 2, 395 final: false, 396 outSize: 1, 397 }, 398 0, 399 }, 400 } 401 402 for _, test := range tests { 403 t.Run(test.desc, func(t *testing.T) { 404 got := test.in.FinalOutput() 405 if got != test.want { 406 t.Errorf("wanted: %d, got: %d", test.want, got) 407 } 408 }) 409 } 410} 411 412func TestDecodeStateZero(t *testing.T) { 413 var state fstStateV1 414 err := state.at(nil, 0) 415 if err != nil { 416 t.Fatal(err) 417 } 418 if state.numTrans != 0 { 419 t.Errorf("expected 0 states, got %d", state.numTrans) 420 } 421 if !state.final { 422 t.Errorf("expected state final, got %t", state.final) 423 } 424} 425 426func TestDecodeAtInvalid(t *testing.T) { 427 var state fstStateV1 428 err := state.at(nil, 15) 429 if err == nil { 430 t.Errorf("expected error invalid address, got nil") 431 } 432} 433 434func TestFSTStateTransitionAt(t *testing.T) { 435 state := fstStateV1{ 436 data: []byte{oneTransition | encodeCommon('a')}, 437 numTrans: 1, 438 singleTransChar: 'a', 439 } 440 got := state.TransitionAt(0) 441 if got != state.singleTransChar { 442 t.Errorf("expected %s got %s", string(state.singleTransChar), string(got)) 443 } 444 445 state = fstStateV1{ 446 data: []byte{'b', 'a'}, 447 numTrans: 2, 448 transBottom: 0, 449 transTop: 2, 450 } 451 got = state.TransitionAt(0) 452 if got != 'a' { 453 t.Errorf("expected %s got %s", string('a'), string(got)) 454 } 455 456} 457