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	"encoding/binary"
20	"fmt"
21	"strconv"
22)
23
24func init() {
25	registerDecoder(versionV1, func(data []byte) decoder {
26		return newDecoderV1(data)
27	})
28}
29
30type decoderV1 struct {
31	data []byte
32}
33
34func newDecoderV1(data []byte) *decoderV1 {
35	return &decoderV1{
36		data: data,
37	}
38}
39
40func (d *decoderV1) getRoot() int {
41	if len(d.data) < footerSizeV1 {
42		return noneAddr
43	}
44	footer := d.data[len(d.data)-footerSizeV1:]
45	root := binary.LittleEndian.Uint64(footer[8:])
46	return int(root)
47}
48
49func (d *decoderV1) getLen() int {
50	if len(d.data) < footerSizeV1 {
51		return 0
52	}
53	footer := d.data[len(d.data)-footerSizeV1:]
54	dlen := binary.LittleEndian.Uint64(footer)
55	return int(dlen)
56}
57
58func (d *decoderV1) stateAt(addr int, prealloc fstState) (fstState, error) {
59	state, ok := prealloc.(*fstStateV1)
60	if ok && state != nil {
61		*state = fstStateV1{} // clear the struct
62	} else {
63		state = &fstStateV1{}
64	}
65	err := state.at(d.data, addr)
66	if err != nil {
67		return nil, err
68	}
69	return state, nil
70}
71
72type fstStateV1 struct {
73	data     []byte
74	top      int
75	bottom   int
76	numTrans int
77
78	// single trans only
79	singleTransChar byte
80	singleTransNext bool
81	singleTransAddr uint64
82	singleTransOut  uint64
83
84	// shared
85	transSize int
86	outSize   int
87
88	// multiple trans only
89	final       bool
90	transTop    int
91	transBottom int
92	destTop     int
93	destBottom  int
94	outTop      int
95	outBottom   int
96	outFinal    int
97}
98
99func (f *fstStateV1) isEncodedSingle() bool {
100	if f.data[f.top]>>7 > 0 {
101		return true
102	}
103	return false
104}
105
106func (f *fstStateV1) at(data []byte, addr int) error {
107	f.data = data
108	if addr == emptyAddr {
109		return f.atZero()
110	} else if addr == noneAddr {
111		return f.atNone()
112	}
113	if addr > len(data) || addr < 16 {
114		return fmt.Errorf("invalid address %d/%d", addr, len(data))
115	}
116	f.top = addr
117	f.bottom = addr
118	if f.isEncodedSingle() {
119		return f.atSingle(data, addr)
120	}
121	return f.atMulti(data, addr)
122}
123
124func (f *fstStateV1) atZero() error {
125	f.top = 0
126	f.bottom = 1
127	f.numTrans = 0
128	f.final = true
129	f.outFinal = 0
130	return nil
131}
132
133func (f *fstStateV1) atNone() error {
134	f.top = 0
135	f.bottom = 1
136	f.numTrans = 0
137	f.final = false
138	f.outFinal = 0
139	return nil
140}
141
142func (f *fstStateV1) atSingle(data []byte, addr int) error {
143	// handle single transition case
144	f.numTrans = 1
145	f.singleTransNext = data[f.top]&transitionNext > 0
146	f.singleTransChar = data[f.top] & maxCommon
147	if f.singleTransChar == 0 {
148		f.bottom-- // extra byte for uncommon
149		f.singleTransChar = data[f.bottom]
150	} else {
151		f.singleTransChar = decodeCommon(f.singleTransChar)
152	}
153	if f.singleTransNext {
154		// now we know the bottom, can compute next addr
155		f.singleTransAddr = uint64(f.bottom - 1)
156		f.singleTransOut = 0
157	} else {
158		f.bottom-- // extra byte with pack sizes
159		f.transSize, f.outSize = decodePackSize(data[f.bottom])
160		f.bottom -= f.transSize // exactly one trans
161		f.singleTransAddr = readPackedUint(data[f.bottom : f.bottom+f.transSize])
162		if f.outSize > 0 {
163			f.bottom -= f.outSize // exactly one out (could be length 0 though)
164			f.singleTransOut = readPackedUint(data[f.bottom : f.bottom+f.outSize])
165		} else {
166			f.singleTransOut = 0
167		}
168		// need to wait till we know bottom
169		if f.singleTransAddr != 0 {
170			f.singleTransAddr = uint64(f.bottom) - f.singleTransAddr
171		}
172	}
173	return nil
174}
175
176func (f *fstStateV1) atMulti(data []byte, addr int) error {
177	// handle multiple transitions case
178	f.final = data[f.top]&stateFinal > 0
179	f.numTrans = int(data[f.top] & maxNumTrans)
180	if f.numTrans == 0 {
181		f.bottom-- // extra byte for number of trans
182		f.numTrans = int(data[f.bottom])
183		if f.numTrans == 1 {
184			// can't really be 1 here, this is special case that means 256
185			f.numTrans = 256
186		}
187	}
188	f.bottom-- // extra byte with pack sizes
189	f.transSize, f.outSize = decodePackSize(data[f.bottom])
190
191	f.transTop = f.bottom
192	f.bottom -= f.numTrans // one byte for each transition
193	f.transBottom = f.bottom
194
195	f.destTop = f.bottom
196	f.bottom -= f.numTrans * f.transSize
197	f.destBottom = f.bottom
198
199	if f.outSize > 0 {
200		f.outTop = f.bottom
201		f.bottom -= f.numTrans * f.outSize
202		f.outBottom = f.bottom
203		if f.final {
204			f.bottom -= f.outSize
205			f.outFinal = f.bottom
206		}
207	}
208	return nil
209}
210
211func (f *fstStateV1) Address() int {
212	return f.top
213}
214
215func (f *fstStateV1) Final() bool {
216	return f.final
217}
218
219func (f *fstStateV1) FinalOutput() uint64 {
220	if f.final && f.outSize > 0 {
221		return readPackedUint(f.data[f.outFinal : f.outFinal+f.outSize])
222	}
223	return 0
224}
225
226func (f *fstStateV1) NumTransitions() int {
227	return f.numTrans
228}
229
230func (f *fstStateV1) TransitionAt(i int) byte {
231	if f.isEncodedSingle() {
232		return f.singleTransChar
233	}
234	transitionKeys := f.data[f.transBottom:f.transTop]
235	return transitionKeys[f.numTrans-i-1]
236}
237
238func (f *fstStateV1) TransitionFor(b byte) (int, int, uint64) {
239	if f.isEncodedSingle() {
240		if f.singleTransChar == b {
241			return 0, int(f.singleTransAddr), f.singleTransOut
242		}
243		return -1, noneAddr, 0
244	}
245	transitionKeys := f.data[f.transBottom:f.transTop]
246	pos := bytes.IndexByte(transitionKeys, b)
247	if pos < 0 {
248		return -1, noneAddr, 0
249	}
250	transDests := f.data[f.destBottom:f.destTop]
251	dest := int(readPackedUint(transDests[pos*f.transSize : pos*f.transSize+f.transSize]))
252	if dest > 0 {
253		// convert delta
254		dest = f.bottom - dest
255	}
256	transVals := f.data[f.outBottom:f.outTop]
257	var out uint64
258	if f.outSize > 0 {
259		out = readPackedUint(transVals[pos*f.outSize : pos*f.outSize+f.outSize])
260	}
261	return f.numTrans - pos - 1, dest, out
262}
263
264func (f *fstStateV1) String() string {
265	rv := ""
266	rv += fmt.Sprintf("State: %d (%#x)", f.top, f.top)
267	if f.final {
268		rv += " final"
269		fout := f.FinalOutput()
270		if fout != 0 {
271			rv += fmt.Sprintf(" (%d)", fout)
272		}
273	}
274	rv += "\n"
275	rv += fmt.Sprintf("Data: % x\n", f.data[f.bottom:f.top+1])
276
277	for i := 0; i < f.numTrans; i++ {
278		transChar := f.TransitionAt(i)
279		_, transDest, transOut := f.TransitionFor(transChar)
280		rv += fmt.Sprintf(" - %d (%#x) '%s' ---> %d (%#x)  with output: %d", transChar, transChar, string(transChar), transDest, transDest, transOut)
281		rv += "\n"
282	}
283	if f.numTrans == 0 {
284		rv += "\n"
285	}
286	return rv
287}
288
289func (f *fstStateV1) DotString(num int) string {
290	rv := ""
291	label := fmt.Sprintf("%d", num)
292	final := ""
293	if f.final {
294		final = ",peripheries=2"
295	}
296	rv += fmt.Sprintf("    %d [label=\"%s\"%s];\n", f.top, label, final)
297
298	for i := 0; i < f.numTrans; i++ {
299		transChar := f.TransitionAt(i)
300		_, transDest, transOut := f.TransitionFor(transChar)
301		out := ""
302		if transOut != 0 {
303			out = fmt.Sprintf("/%d", transOut)
304		}
305		rv += fmt.Sprintf("    %d -> %d [label=\"%s%s\"];\n", f.top, transDest, escapeInput(transChar), out)
306	}
307
308	return rv
309}
310
311func escapeInput(b byte) string {
312	x := strconv.AppendQuoteRune(nil, rune(b))
313	return string(x[1:(len(x) - 1)])
314}
315