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	"reflect"
20	"testing"
21)
22
23// FIXME add tests for longjmp (wider delta address)
24// FIXME add tests for wider values
25// FIXME add tests for mixed value sizes in same edge (fixed size, but padded)
26// FIXME add test for final state (must include final val even if 0)
27
28func TestEncoderVersionError(t *testing.T) {
29	_, err := loadEncoder(629, nil)
30	if err == nil {
31		t.Errorf("expected error loading encoder version 629, got nil")
32	}
33}
34
35func TestEncoderStart(t *testing.T) {
36
37	var headerV1 = []byte{
38		1, 0, 0, 0, 0, 0, 0, 0,
39		0, 0, 0, 0, 0, 0, 0, 0,
40	}
41
42	var buf bytes.Buffer
43	e := newEncoderV1(&buf)
44	err := e.start()
45	if err != nil {
46		t.Fatal(err)
47	}
48	// manually flush
49	err = e.bw.Flush()
50	if err != nil {
51		t.Fatal(err)
52	}
53	got := buf.Bytes()
54	if !reflect.DeepEqual(got, headerV1) {
55		t.Errorf("expected header: %v, got %v", headerV1, got)
56	}
57}
58
59func TestEncoderStateOneNextWithCommonInput(t *testing.T) {
60
61	curr := &builderNode{
62		trans: []transition{
63			{
64				in:   'a',
65				addr: 27,
66			},
67		},
68	}
69
70	var buf bytes.Buffer
71	e := newEncoderV1(&buf)
72
73	// now encode the curr state
74	_, err := e.encodeState(curr, 27)
75	if err != nil {
76		t.Fatal(err)
77	}
78
79	// manually flush
80	err = e.bw.Flush()
81	if err != nil {
82		t.Fatal(err)
83	}
84
85	// now look at the bytes produced
86	var want = []byte{
87		oneTransition | transitionNext | encodeCommon('a'),
88	}
89	got := buf.Bytes()
90	if !reflect.DeepEqual(got, want) {
91		t.Errorf("expected bytes: %v, got %v", want, got)
92	}
93}
94
95func TestEncoderStateOneNextWithUncommonInput(t *testing.T) {
96
97	curr := &builderNode{
98		trans: []transition{
99			{
100				in:   0xff,
101				addr: 27,
102			},
103		},
104	}
105
106	var buf bytes.Buffer
107	e := newEncoderV1(&buf)
108
109	// now encode the curr state
110	_, err := e.encodeState(curr, 27)
111	if err != nil {
112		t.Fatal(err)
113	}
114
115	// manually flush
116	err = e.bw.Flush()
117	if err != nil {
118		t.Fatal(err)
119	}
120
121	// now look at the bytes produced
122	var want = []byte{
123		0xff,
124		oneTransition | transitionNext,
125	}
126	got := buf.Bytes()
127	if !reflect.DeepEqual(got, want) {
128		t.Errorf("expected bytes: %v, got %v", want, got)
129	}
130}
131
132func TestEncoderStateOneNotNextWithCommonInputNoValue(t *testing.T) {
133
134	curr := &builderNode{
135		trans: []transition{
136			{
137				in:   'a',
138				addr: 32,
139			},
140		},
141	}
142
143	var buf bytes.Buffer
144	e := newEncoderV1(&buf)
145
146	// pretend we're at a position in the file
147	e.bw.counter = 64
148
149	// now encode the curr state
150	_, err := e.encodeState(curr, 64)
151	if err != nil {
152		t.Fatal(err)
153	}
154
155	// manually flush
156	err = e.bw.Flush()
157	if err != nil {
158		t.Fatal(err)
159	}
160
161	// now look at the bytes produced
162	var want = []byte{
163		32,       // delta address packed
164		1<<4 | 0, // pack sizes
165		oneTransition | encodeCommon('a'),
166	}
167	got := buf.Bytes()
168	if !reflect.DeepEqual(got, want) {
169		t.Errorf("expected bytes: %v, got %v", want, got)
170	}
171}
172
173func TestEncoderStateOneNotNextWithUncommonInputNoValue(t *testing.T) {
174
175	curr := &builderNode{
176		trans: []transition{
177			{
178				in:   0xff,
179				addr: 32,
180			},
181		},
182	}
183
184	var buf bytes.Buffer
185	e := newEncoderV1(&buf)
186
187	// pretend we're at a position in the file
188	e.bw.counter = 64
189
190	// now encode the curr state
191	_, err := e.encodeState(curr, 64)
192	if err != nil {
193		t.Fatal(err)
194	}
195
196	// manually flush
197	err = e.bw.Flush()
198	if err != nil {
199		t.Fatal(err)
200	}
201
202	// now look at the bytes produced
203	var want = []byte{
204		32,       // delta address packed
205		1<<4 | 0, // pack sizes
206		0xff,
207		oneTransition,
208	}
209	got := buf.Bytes()
210	if !reflect.DeepEqual(got, want) {
211		t.Errorf("expected bytes: %v, got %v", want, got)
212	}
213}
214
215func TestEncoderStateOneNotNextWithCommonInputWithValue(t *testing.T) {
216
217	curr := &builderNode{
218		trans: []transition{
219			{
220				in:   'a',
221				addr: 32,
222				out:  27,
223			},
224		},
225	}
226
227	var buf bytes.Buffer
228	e := newEncoderV1(&buf)
229
230	// pretend we're at a position in the file
231	e.bw.counter = 64
232
233	// now encode the curr state
234	_, err := e.encodeState(curr, 64)
235	if err != nil {
236		t.Fatal(err)
237	}
238
239	// manually flush
240	err = e.bw.Flush()
241	if err != nil {
242		t.Fatal(err)
243	}
244
245	// now look at the bytes produced
246	var want = []byte{
247		27,       // trans value
248		32,       // delta address packed
249		1<<4 | 1, // pack sizes
250		oneTransition | encodeCommon('a'),
251	}
252	got := buf.Bytes()
253	if !reflect.DeepEqual(got, want) {
254		t.Errorf("expected bytes: %v, got %v", want, got)
255	}
256}
257
258func TestEncoderStateOneNotNextWithUncommonInputWithValue(t *testing.T) {
259
260	curr := &builderNode{
261		trans: []transition{
262			{
263				in:   0xff,
264				addr: 32,
265				out:  39,
266			},
267		},
268	}
269
270	var buf bytes.Buffer
271	e := newEncoderV1(&buf)
272
273	// pretend we're at a position in the file
274	e.bw.counter = 64
275
276	// now encode the curr state
277	_, err := e.encodeState(curr, 64)
278	if err != nil {
279		t.Fatal(err)
280	}
281
282	// manually flush
283	err = e.bw.Flush()
284	if err != nil {
285		t.Fatal(err)
286	}
287
288	// now look at the bytes produced
289	var want = []byte{
290		39,       // trans val
291		32,       // delta address packed
292		1<<4 | 1, // pack sizes
293		0xff,
294		oneTransition,
295	}
296	got := buf.Bytes()
297	if !reflect.DeepEqual(got, want) {
298		t.Errorf("expected bytes: %v, got %v", want, got)
299	}
300}
301
302func TestEncoderStateManyWithNoValues(t *testing.T) {
303
304	curr := &builderNode{
305		trans: []transition{
306			{
307				in:   'a',
308				addr: 32,
309			},
310			{
311				in:   'b',
312				addr: 45,
313			},
314			{
315				in:   'c',
316				addr: 52,
317			},
318		},
319	}
320
321	var buf bytes.Buffer
322	e := newEncoderV1(&buf)
323
324	// pretend we're at a position in the file
325	e.bw.counter = 64
326
327	// now encode the curr state
328	_, err := e.encodeState(curr, 64)
329	if err != nil {
330		t.Fatal(err)
331	}
332
333	// manually flush
334	err = e.bw.Flush()
335	if err != nil {
336		t.Fatal(err)
337	}
338
339	// now look at the bytes produced
340	var want = []byte{
341		12, // delta addresses packed
342		19,
343		32,
344		'c', // encoded keys reversed
345		'b',
346		'a',
347		1<<4 | 0, // pack sizes
348		encodeNumTrans(3),
349	}
350	got := buf.Bytes()
351	if !reflect.DeepEqual(got, want) {
352		t.Errorf("expected bytes: %v, got %v", want, got)
353	}
354}
355
356func TestEncoderStateManyWithValues(t *testing.T) {
357
358	curr := &builderNode{
359		trans: []transition{
360			{
361				in:   'a',
362				addr: 32,
363				out:  3,
364			},
365			{
366				in:   'b',
367				addr: 45,
368				out:  0,
369			},
370			{
371				in:   'c',
372				addr: 52,
373				out:  7,
374			},
375		},
376	}
377
378	var buf bytes.Buffer
379	e := newEncoderV1(&buf)
380
381	// pretend we're at a position in the file
382	e.bw.counter = 64
383
384	// now encode the curr state
385	_, err := e.encodeState(curr, 64)
386	if err != nil {
387		t.Fatal(err)
388	}
389
390	// manually flush
391	err = e.bw.Flush()
392	if err != nil {
393		t.Fatal(err)
394	}
395
396	// now look at the bytes produced
397	var want = []byte{
398		7, // values reversed
399		0,
400		3,
401		12, // delta addresses reversed
402		19,
403		32,
404		'c', // encoded keys reversed
405		'b',
406		'a',
407		1<<4 | 1, // pack sizes
408		encodeNumTrans(3),
409	}
410	got := buf.Bytes()
411	if !reflect.DeepEqual(got, want) {
412		t.Errorf("expected bytes: %v, got %v", want, got)
413	}
414}
415
416func TestEncoderStateMaxTransitions(t *testing.T) {
417	testEncoderStateNTransitions(t, 256)
418}
419
420func TestEncoderStateMoreTransitionsThanFitInHeader(t *testing.T) {
421	testEncoderStateNTransitions(t, 1<<6)
422}
423
424func testEncoderStateNTransitions(t *testing.T, n int) {
425
426	curr := &builderNode{
427		trans: make([]transition, n),
428	}
429	for i := 0; i < n; i++ {
430		curr.trans[i] = transition{
431			in:   byte(i),
432			addr: 32,
433		}
434	}
435
436	var buf bytes.Buffer
437	e := newEncoderV1(&buf)
438
439	// pretend we're at a position in the file
440	e.bw.counter = 64
441
442	// now encode the curr state
443	_, err := e.encodeState(curr, 64)
444	if err != nil {
445		t.Fatal(err)
446	}
447
448	// manually flush
449	err = e.bw.Flush()
450	if err != nil {
451		t.Fatal(err)
452	}
453
454	// now look at the bytes produced
455	var want []byte
456	// append 256 delta addresses
457	for i := 0; i < n; i++ {
458		want = append(want, 32)
459	}
460	// append transition keys (reversed)
461	for i := n - 1; i >= 0; i-- {
462		want = append(want, byte(i))
463	}
464	// append pack sizes
465	want = append(want, 1<<4|0)
466
467	if n > 1<<6-1 {
468		// append separate byte of pack sizes
469		if n == 256 { // 256 is specially encoded as 1
470			want = append(want, 1)
471		} else {
472			want = append(want, byte(n))
473		}
474
475	}
476	// append header byte, which is all 0 in this case
477	want = append(want, 0)
478	got := buf.Bytes()
479	if !reflect.DeepEqual(got, want) {
480		t.Errorf("expected bytes: %v, got %v", want, got)
481	}
482}
483