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