1/*
2  Based on the "jsonpath" spec/concept.
3
4  http://goessner.net/articles/JsonPath/
5  https://code.google.com/p/json-path/
6*/
7
8package query
9
10import (
11	"fmt"
12)
13
14const maxInt = int(^uint(0) >> 1)
15
16type queryParser struct {
17	flow         chan token
18	tokensBuffer []token
19	query        *Query
20	union        []pathFn
21	err          error
22}
23
24type queryParserStateFn func() queryParserStateFn
25
26// Formats and panics an error message based on a token
27func (p *queryParser) parseError(tok *token, msg string, args ...interface{}) queryParserStateFn {
28	p.err = fmt.Errorf(tok.Position.String()+": "+msg, args...)
29	return nil // trigger parse to end
30}
31
32func (p *queryParser) run() {
33	for state := p.parseStart; state != nil; {
34		state = state()
35	}
36}
37
38func (p *queryParser) backup(tok *token) {
39	p.tokensBuffer = append(p.tokensBuffer, *tok)
40}
41
42func (p *queryParser) peek() *token {
43	if len(p.tokensBuffer) != 0 {
44		return &(p.tokensBuffer[0])
45	}
46
47	tok, ok := <-p.flow
48	if !ok {
49		return nil
50	}
51	p.backup(&tok)
52	return &tok
53}
54
55func (p *queryParser) lookahead(types ...tokenType) bool {
56	result := true
57	buffer := []token{}
58
59	for _, typ := range types {
60		tok := p.getToken()
61		if tok == nil {
62			result = false
63			break
64		}
65		buffer = append(buffer, *tok)
66		if tok.typ != typ {
67			result = false
68			break
69		}
70	}
71	// add the tokens back to the buffer, and return
72	p.tokensBuffer = append(p.tokensBuffer, buffer...)
73	return result
74}
75
76func (p *queryParser) getToken() *token {
77	if len(p.tokensBuffer) != 0 {
78		tok := p.tokensBuffer[0]
79		p.tokensBuffer = p.tokensBuffer[1:]
80		return &tok
81	}
82	tok, ok := <-p.flow
83	if !ok {
84		return nil
85	}
86	return &tok
87}
88
89func (p *queryParser) parseStart() queryParserStateFn {
90	tok := p.getToken()
91
92	if tok == nil || tok.typ == tokenEOF {
93		return nil
94	}
95
96	if tok.typ != tokenDollar {
97		return p.parseError(tok, "Expected '$' at start of expression")
98	}
99
100	return p.parseMatchExpr
101}
102
103// handle '.' prefix, '[]', and '..'
104func (p *queryParser) parseMatchExpr() queryParserStateFn {
105	tok := p.getToken()
106	switch tok.typ {
107	case tokenDotDot:
108		p.query.appendPath(&matchRecursiveFn{})
109		// nested parse for '..'
110		tok := p.getToken()
111		switch tok.typ {
112		case tokenKey:
113			p.query.appendPath(newMatchKeyFn(tok.val))
114			return p.parseMatchExpr
115		case tokenLeftBracket:
116			return p.parseBracketExpr
117		case tokenStar:
118			// do nothing - the recursive predicate is enough
119			return p.parseMatchExpr
120		}
121
122	case tokenDot:
123		// nested parse for '.'
124		tok := p.getToken()
125		switch tok.typ {
126		case tokenKey:
127			p.query.appendPath(newMatchKeyFn(tok.val))
128			return p.parseMatchExpr
129		case tokenStar:
130			p.query.appendPath(&matchAnyFn{})
131			return p.parseMatchExpr
132		}
133
134	case tokenLeftBracket:
135		return p.parseBracketExpr
136
137	case tokenEOF:
138		return nil // allow EOF at this stage
139	}
140	return p.parseError(tok, "expected match expression")
141}
142
143func (p *queryParser) parseBracketExpr() queryParserStateFn {
144	if p.lookahead(tokenInteger, tokenColon) {
145		return p.parseSliceExpr
146	}
147	if p.peek().typ == tokenColon {
148		return p.parseSliceExpr
149	}
150	return p.parseUnionExpr
151}
152
153func (p *queryParser) parseUnionExpr() queryParserStateFn {
154	var tok *token
155
156	// this state can be traversed after some sub-expressions
157	// so be careful when setting up state in the parser
158	if p.union == nil {
159		p.union = []pathFn{}
160	}
161
162loop: // labeled loop for easy breaking
163	for {
164		if len(p.union) > 0 {
165			// parse delimiter or terminator
166			tok = p.getToken()
167			switch tok.typ {
168			case tokenComma:
169				// do nothing
170			case tokenRightBracket:
171				break loop
172			default:
173				return p.parseError(tok, "expected ',' or ']', not '%s'", tok.val)
174			}
175		}
176
177		// parse sub expression
178		tok = p.getToken()
179		switch tok.typ {
180		case tokenInteger:
181			p.union = append(p.union, newMatchIndexFn(tok.Int()))
182		case tokenKey:
183			p.union = append(p.union, newMatchKeyFn(tok.val))
184		case tokenString:
185			p.union = append(p.union, newMatchKeyFn(tok.val))
186		case tokenQuestion:
187			return p.parseFilterExpr
188		default:
189			return p.parseError(tok, "expected union sub expression, not '%s', %d", tok.val, len(p.union))
190		}
191	}
192
193	// if there is only one sub-expression, use that instead
194	if len(p.union) == 1 {
195		p.query.appendPath(p.union[0])
196	} else {
197		p.query.appendPath(&matchUnionFn{p.union})
198	}
199
200	p.union = nil // clear out state
201	return p.parseMatchExpr
202}
203
204func (p *queryParser) parseSliceExpr() queryParserStateFn {
205	// init slice to grab all elements
206	var start, end, step *int = nil, nil, nil
207
208	// parse optional start
209	tok := p.getToken()
210	if tok.typ == tokenInteger {
211		v := tok.Int()
212		start = &v
213		tok = p.getToken()
214	}
215	if tok.typ != tokenColon {
216		return p.parseError(tok, "expected ':'")
217	}
218
219	// parse optional end
220	tok = p.getToken()
221	if tok.typ == tokenInteger {
222		v := tok.Int()
223		end = &v
224		tok = p.getToken()
225	}
226	if tok.typ == tokenRightBracket {
227		p.query.appendPath(&matchSliceFn{Start: start, End: end, Step: step})
228		return p.parseMatchExpr
229	}
230	if tok.typ != tokenColon {
231		return p.parseError(tok, "expected ']' or ':'")
232	}
233
234	// parse optional step
235	tok = p.getToken()
236	if tok.typ == tokenInteger {
237		v := tok.Int()
238		if v == 0 {
239			return p.parseError(tok, "step cannot be zero")
240		}
241		step = &v
242		tok = p.getToken()
243	}
244	if tok.typ != tokenRightBracket {
245		return p.parseError(tok, "expected ']'")
246	}
247
248	p.query.appendPath(&matchSliceFn{Start: start, End: end, Step: step})
249	return p.parseMatchExpr
250}
251
252func (p *queryParser) parseFilterExpr() queryParserStateFn {
253	tok := p.getToken()
254	if tok.typ != tokenLeftParen {
255		return p.parseError(tok, "expected left-parenthesis for filter expression")
256	}
257	tok = p.getToken()
258	if tok.typ != tokenKey && tok.typ != tokenString {
259		return p.parseError(tok, "expected key or string for filter function name")
260	}
261	name := tok.val
262	tok = p.getToken()
263	if tok.typ != tokenRightParen {
264		return p.parseError(tok, "expected right-parenthesis for filter expression")
265	}
266	p.union = append(p.union, newMatchFilterFn(name, tok.Position))
267	return p.parseUnionExpr
268}
269
270func parseQuery(flow chan token) (*Query, error) {
271	parser := &queryParser{
272		flow:         flow,
273		tokensBuffer: []token{},
274		query:        newQuery(),
275	}
276	parser.run()
277	return parser.query, parser.err
278}
279