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