]>
Commit | Line | Data |
---|---|---|
bae9f6d2 JC |
1 | package jmespath |
2 | ||
3 | import ( | |
4 | "bytes" | |
5 | "encoding/json" | |
6 | "fmt" | |
7 | "strconv" | |
8 | "strings" | |
9 | "unicode/utf8" | |
10 | ) | |
11 | ||
12 | type token struct { | |
13 | tokenType tokType | |
14 | value string | |
15 | position int | |
16 | length int | |
17 | } | |
18 | ||
19 | type tokType int | |
20 | ||
21 | const eof = -1 | |
22 | ||
23 | // Lexer contains information about the expression being tokenized. | |
24 | type Lexer struct { | |
25 | expression string // The expression provided by the user. | |
26 | currentPos int // The current position in the string. | |
27 | lastWidth int // The width of the current rune. This | |
28 | buf bytes.Buffer // Internal buffer used for building up values. | |
29 | } | |
30 | ||
31 | // SyntaxError is the main error used whenever a lexing or parsing error occurs. | |
32 | type SyntaxError struct { | |
33 | msg string // Error message displayed to user | |
34 | Expression string // Expression that generated a SyntaxError | |
35 | Offset int // The location in the string where the error occurred | |
36 | } | |
37 | ||
38 | func (e SyntaxError) Error() string { | |
39 | // In the future, it would be good to underline the specific | |
40 | // location where the error occurred. | |
41 | return "SyntaxError: " + e.msg | |
42 | } | |
43 | ||
44 | // HighlightLocation will show where the syntax error occurred. | |
45 | // It will place a "^" character on a line below the expression | |
46 | // at the point where the syntax error occurred. | |
47 | func (e SyntaxError) HighlightLocation() string { | |
48 | return e.Expression + "\n" + strings.Repeat(" ", e.Offset) + "^" | |
49 | } | |
50 | ||
51 | //go:generate stringer -type=tokType | |
52 | const ( | |
53 | tUnknown tokType = iota | |
54 | tStar | |
55 | tDot | |
56 | tFilter | |
57 | tFlatten | |
58 | tLparen | |
59 | tRparen | |
60 | tLbracket | |
61 | tRbracket | |
62 | tLbrace | |
63 | tRbrace | |
64 | tOr | |
65 | tPipe | |
66 | tNumber | |
67 | tUnquotedIdentifier | |
68 | tQuotedIdentifier | |
69 | tComma | |
70 | tColon | |
71 | tLT | |
72 | tLTE | |
73 | tGT | |
74 | tGTE | |
75 | tEQ | |
76 | tNE | |
77 | tJSONLiteral | |
78 | tStringLiteral | |
79 | tCurrent | |
80 | tExpref | |
81 | tAnd | |
82 | tNot | |
83 | tEOF | |
84 | ) | |
85 | ||
86 | var basicTokens = map[rune]tokType{ | |
87 | '.': tDot, | |
88 | '*': tStar, | |
89 | ',': tComma, | |
90 | ':': tColon, | |
91 | '{': tLbrace, | |
92 | '}': tRbrace, | |
93 | ']': tRbracket, // tLbracket not included because it could be "[]" | |
94 | '(': tLparen, | |
95 | ')': tRparen, | |
96 | '@': tCurrent, | |
97 | } | |
98 | ||
99 | // Bit mask for [a-zA-Z_] shifted down 64 bits to fit in a single uint64. | |
100 | // When using this bitmask just be sure to shift the rune down 64 bits | |
101 | // before checking against identifierStartBits. | |
102 | const identifierStartBits uint64 = 576460745995190270 | |
103 | ||
104 | // Bit mask for [a-zA-Z0-9], 128 bits -> 2 uint64s. | |
105 | var identifierTrailingBits = [2]uint64{287948901175001088, 576460745995190270} | |
106 | ||
107 | var whiteSpace = map[rune]bool{ | |
108 | ' ': true, '\t': true, '\n': true, '\r': true, | |
109 | } | |
110 | ||
111 | func (t token) String() string { | |
112 | return fmt.Sprintf("Token{%+v, %s, %d, %d}", | |
113 | t.tokenType, t.value, t.position, t.length) | |
114 | } | |
115 | ||
116 | // NewLexer creates a new JMESPath lexer. | |
117 | func NewLexer() *Lexer { | |
118 | lexer := Lexer{} | |
119 | return &lexer | |
120 | } | |
121 | ||
122 | func (lexer *Lexer) next() rune { | |
123 | if lexer.currentPos >= len(lexer.expression) { | |
124 | lexer.lastWidth = 0 | |
125 | return eof | |
126 | } | |
127 | r, w := utf8.DecodeRuneInString(lexer.expression[lexer.currentPos:]) | |
128 | lexer.lastWidth = w | |
129 | lexer.currentPos += w | |
130 | return r | |
131 | } | |
132 | ||
133 | func (lexer *Lexer) back() { | |
134 | lexer.currentPos -= lexer.lastWidth | |
135 | } | |
136 | ||
137 | func (lexer *Lexer) peek() rune { | |
138 | t := lexer.next() | |
139 | lexer.back() | |
140 | return t | |
141 | } | |
142 | ||
143 | // tokenize takes an expression and returns corresponding tokens. | |
144 | func (lexer *Lexer) tokenize(expression string) ([]token, error) { | |
145 | var tokens []token | |
146 | lexer.expression = expression | |
147 | lexer.currentPos = 0 | |
148 | lexer.lastWidth = 0 | |
149 | loop: | |
150 | for { | |
151 | r := lexer.next() | |
152 | if identifierStartBits&(1<<(uint64(r)-64)) > 0 { | |
153 | t := lexer.consumeUnquotedIdentifier() | |
154 | tokens = append(tokens, t) | |
155 | } else if val, ok := basicTokens[r]; ok { | |
156 | // Basic single char token. | |
157 | t := token{ | |
158 | tokenType: val, | |
159 | value: string(r), | |
160 | position: lexer.currentPos - lexer.lastWidth, | |
161 | length: 1, | |
162 | } | |
163 | tokens = append(tokens, t) | |
164 | } else if r == '-' || (r >= '0' && r <= '9') { | |
165 | t := lexer.consumeNumber() | |
166 | tokens = append(tokens, t) | |
167 | } else if r == '[' { | |
168 | t := lexer.consumeLBracket() | |
169 | tokens = append(tokens, t) | |
170 | } else if r == '"' { | |
171 | t, err := lexer.consumeQuotedIdentifier() | |
172 | if err != nil { | |
173 | return tokens, err | |
174 | } | |
175 | tokens = append(tokens, t) | |
176 | } else if r == '\'' { | |
177 | t, err := lexer.consumeRawStringLiteral() | |
178 | if err != nil { | |
179 | return tokens, err | |
180 | } | |
181 | tokens = append(tokens, t) | |
182 | } else if r == '`' { | |
183 | t, err := lexer.consumeLiteral() | |
184 | if err != nil { | |
185 | return tokens, err | |
186 | } | |
187 | tokens = append(tokens, t) | |
188 | } else if r == '|' { | |
189 | t := lexer.matchOrElse(r, '|', tOr, tPipe) | |
190 | tokens = append(tokens, t) | |
191 | } else if r == '<' { | |
192 | t := lexer.matchOrElse(r, '=', tLTE, tLT) | |
193 | tokens = append(tokens, t) | |
194 | } else if r == '>' { | |
195 | t := lexer.matchOrElse(r, '=', tGTE, tGT) | |
196 | tokens = append(tokens, t) | |
197 | } else if r == '!' { | |
198 | t := lexer.matchOrElse(r, '=', tNE, tNot) | |
199 | tokens = append(tokens, t) | |
200 | } else if r == '=' { | |
201 | t := lexer.matchOrElse(r, '=', tEQ, tUnknown) | |
202 | tokens = append(tokens, t) | |
203 | } else if r == '&' { | |
204 | t := lexer.matchOrElse(r, '&', tAnd, tExpref) | |
205 | tokens = append(tokens, t) | |
206 | } else if r == eof { | |
207 | break loop | |
208 | } else if _, ok := whiteSpace[r]; ok { | |
209 | // Ignore whitespace | |
210 | } else { | |
211 | return tokens, lexer.syntaxError(fmt.Sprintf("Unknown char: %s", strconv.QuoteRuneToASCII(r))) | |
212 | } | |
213 | } | |
214 | tokens = append(tokens, token{tEOF, "", len(lexer.expression), 0}) | |
215 | return tokens, nil | |
216 | } | |
217 | ||
218 | // Consume characters until the ending rune "r" is reached. | |
219 | // If the end of the expression is reached before seeing the | |
220 | // terminating rune "r", then an error is returned. | |
221 | // If no error occurs then the matching substring is returned. | |
222 | // The returned string will not include the ending rune. | |
223 | func (lexer *Lexer) consumeUntil(end rune) (string, error) { | |
224 | start := lexer.currentPos | |
225 | current := lexer.next() | |
226 | for current != end && current != eof { | |
227 | if current == '\\' && lexer.peek() != eof { | |
228 | lexer.next() | |
229 | } | |
230 | current = lexer.next() | |
231 | } | |
232 | if lexer.lastWidth == 0 { | |
233 | // Then we hit an EOF so we never reached the closing | |
234 | // delimiter. | |
235 | return "", SyntaxError{ | |
236 | msg: "Unclosed delimiter: " + string(end), | |
237 | Expression: lexer.expression, | |
238 | Offset: len(lexer.expression), | |
239 | } | |
240 | } | |
241 | return lexer.expression[start : lexer.currentPos-lexer.lastWidth], nil | |
242 | } | |
243 | ||
244 | func (lexer *Lexer) consumeLiteral() (token, error) { | |
245 | start := lexer.currentPos | |
246 | value, err := lexer.consumeUntil('`') | |
247 | if err != nil { | |
248 | return token{}, err | |
249 | } | |
250 | value = strings.Replace(value, "\\`", "`", -1) | |
251 | return token{ | |
252 | tokenType: tJSONLiteral, | |
253 | value: value, | |
254 | position: start, | |
255 | length: len(value), | |
256 | }, nil | |
257 | } | |
258 | ||
259 | func (lexer *Lexer) consumeRawStringLiteral() (token, error) { | |
260 | start := lexer.currentPos | |
261 | currentIndex := start | |
262 | current := lexer.next() | |
263 | for current != '\'' && lexer.peek() != eof { | |
264 | if current == '\\' && lexer.peek() == '\'' { | |
265 | chunk := lexer.expression[currentIndex : lexer.currentPos-1] | |
266 | lexer.buf.WriteString(chunk) | |
267 | lexer.buf.WriteString("'") | |
268 | lexer.next() | |
269 | currentIndex = lexer.currentPos | |
270 | } | |
271 | current = lexer.next() | |
272 | } | |
273 | if lexer.lastWidth == 0 { | |
274 | // Then we hit an EOF so we never reached the closing | |
275 | // delimiter. | |
276 | return token{}, SyntaxError{ | |
277 | msg: "Unclosed delimiter: '", | |
278 | Expression: lexer.expression, | |
279 | Offset: len(lexer.expression), | |
280 | } | |
281 | } | |
282 | if currentIndex < lexer.currentPos { | |
283 | lexer.buf.WriteString(lexer.expression[currentIndex : lexer.currentPos-1]) | |
284 | } | |
285 | value := lexer.buf.String() | |
286 | // Reset the buffer so it can reused again. | |
287 | lexer.buf.Reset() | |
288 | return token{ | |
289 | tokenType: tStringLiteral, | |
290 | value: value, | |
291 | position: start, | |
292 | length: len(value), | |
293 | }, nil | |
294 | } | |
295 | ||
296 | func (lexer *Lexer) syntaxError(msg string) SyntaxError { | |
297 | return SyntaxError{ | |
298 | msg: msg, | |
299 | Expression: lexer.expression, | |
300 | Offset: lexer.currentPos - 1, | |
301 | } | |
302 | } | |
303 | ||
304 | // Checks for a two char token, otherwise matches a single character | |
305 | // token. This is used whenever a two char token overlaps a single | |
306 | // char token, e.g. "||" -> tPipe, "|" -> tOr. | |
307 | func (lexer *Lexer) matchOrElse(first rune, second rune, matchedType tokType, singleCharType tokType) token { | |
308 | start := lexer.currentPos - lexer.lastWidth | |
309 | nextRune := lexer.next() | |
310 | var t token | |
311 | if nextRune == second { | |
312 | t = token{ | |
313 | tokenType: matchedType, | |
314 | value: string(first) + string(second), | |
315 | position: start, | |
316 | length: 2, | |
317 | } | |
318 | } else { | |
319 | lexer.back() | |
320 | t = token{ | |
321 | tokenType: singleCharType, | |
322 | value: string(first), | |
323 | position: start, | |
324 | length: 1, | |
325 | } | |
326 | } | |
327 | return t | |
328 | } | |
329 | ||
330 | func (lexer *Lexer) consumeLBracket() token { | |
331 | // There's three options here: | |
332 | // 1. A filter expression "[?" | |
333 | // 2. A flatten operator "[]" | |
334 | // 3. A bare rbracket "[" | |
335 | start := lexer.currentPos - lexer.lastWidth | |
336 | nextRune := lexer.next() | |
337 | var t token | |
338 | if nextRune == '?' { | |
339 | t = token{ | |
340 | tokenType: tFilter, | |
341 | value: "[?", | |
342 | position: start, | |
343 | length: 2, | |
344 | } | |
345 | } else if nextRune == ']' { | |
346 | t = token{ | |
347 | tokenType: tFlatten, | |
348 | value: "[]", | |
349 | position: start, | |
350 | length: 2, | |
351 | } | |
352 | } else { | |
353 | t = token{ | |
354 | tokenType: tLbracket, | |
355 | value: "[", | |
356 | position: start, | |
357 | length: 1, | |
358 | } | |
359 | lexer.back() | |
360 | } | |
361 | return t | |
362 | } | |
363 | ||
364 | func (lexer *Lexer) consumeQuotedIdentifier() (token, error) { | |
365 | start := lexer.currentPos | |
366 | value, err := lexer.consumeUntil('"') | |
367 | if err != nil { | |
368 | return token{}, err | |
369 | } | |
370 | var decoded string | |
371 | asJSON := []byte("\"" + value + "\"") | |
372 | if err := json.Unmarshal([]byte(asJSON), &decoded); err != nil { | |
373 | return token{}, err | |
374 | } | |
375 | return token{ | |
376 | tokenType: tQuotedIdentifier, | |
377 | value: decoded, | |
378 | position: start - 1, | |
379 | length: len(decoded), | |
380 | }, nil | |
381 | } | |
382 | ||
383 | func (lexer *Lexer) consumeUnquotedIdentifier() token { | |
384 | // Consume runes until we reach the end of an unquoted | |
385 | // identifier. | |
386 | start := lexer.currentPos - lexer.lastWidth | |
387 | for { | |
388 | r := lexer.next() | |
389 | if r < 0 || r > 128 || identifierTrailingBits[uint64(r)/64]&(1<<(uint64(r)%64)) == 0 { | |
390 | lexer.back() | |
391 | break | |
392 | } | |
393 | } | |
394 | value := lexer.expression[start:lexer.currentPos] | |
395 | return token{ | |
396 | tokenType: tUnquotedIdentifier, | |
397 | value: value, | |
398 | position: start, | |
399 | length: lexer.currentPos - start, | |
400 | } | |
401 | } | |
402 | ||
403 | func (lexer *Lexer) consumeNumber() token { | |
404 | // Consume runes until we reach something that's not a number. | |
405 | start := lexer.currentPos - lexer.lastWidth | |
406 | for { | |
407 | r := lexer.next() | |
408 | if r < '0' || r > '9' { | |
409 | lexer.back() | |
410 | break | |
411 | } | |
412 | } | |
413 | value := lexer.expression[start:lexer.currentPos] | |
414 | return token{ | |
415 | tokenType: tNumber, | |
416 | value: value, | |
417 | position: start, | |
418 | length: lexer.currentPos - start, | |
419 | } | |
420 | } |