1 // Copyright 2010 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
7 // JSON value parser state machine.
8 // Just about at the limit of what is reasonable to write by hand.
9 // Some parts are a bit tedious, but overall it nicely factors out the
10 // otherwise common code from the multiple scanning functions
11 // in this package (Compact, Indent, checkValid, etc).
13 // This file starts with two simple examples using the scanner
14 // before diving into the scanner itself.
18 // Valid reports whether data is a valid JSON encoding.
19 func Valid(data
[]byte) bool {
20 return checkValid(data
, &scanner
{}) == nil
23 // checkValid verifies that data is valid JSON-encoded data.
24 // scan is passed in for use by checkValid to avoid an allocation.
25 func checkValid(data
[]byte, scan
*scanner
) error
{
27 for _
, c
:= range data
{
29 if scan
.step(scan
, c
) == scanError
{
33 if scan
.eof() == scanError
{
39 // A SyntaxError is a description of a JSON syntax error.
40 type SyntaxError
struct {
41 msg
string // description of error
42 Offset
int64 // error occurred after reading Offset bytes
45 func (e
*SyntaxError
) Error() string { return e
.msg
}
47 // A scanner is a JSON scanning state machine.
48 // Callers call scan.reset() and then pass bytes in one at a time
49 // by calling scan.step(&scan, c) for each byte.
50 // The return value, referred to as an opcode, tells the
51 // caller about significant parsing events like beginning
52 // and ending literals, objects, and arrays, so that the
53 // caller can follow along if it wishes.
54 // The return value scanEnd indicates that a single top-level
55 // JSON value has been completed, *before* the byte that
56 // just got passed in. (The indication must be delayed in order
57 // to recognize the end of numbers: is 123 a whole value or
58 // the beginning of 12345e+6?).
60 // The step is a func to be called to execute the next transition.
61 // Also tried using an integer constant and a single func
62 // with a switch, but using the func directly was 10% faster
63 // on a 64-bit Mac Mini, and it's nicer to read.
64 step
func(*scanner
, byte) int
66 // Reached end of top-level value.
69 // Stack of what we're in the middle of - array values, object keys, object values.
72 // Error that happened, if any.
75 // total bytes consumed, updated by decoder.Decode
79 // These values are returned by the state transition functions
80 // assigned to scanner.state and the method scanner.eof.
81 // They give details about the current state of the scan that
82 // callers might be interested to know about.
83 // It is okay to ignore the return value of any particular
84 // call to scanner.state: if one call returns scanError,
85 // every subsequent call will return scanError too.
88 scanContinue
= iota // uninteresting byte
89 scanBeginLiteral
// end implied by next result != scanContinue
90 scanBeginObject
// begin object
91 scanObjectKey
// just finished object key (string)
92 scanObjectValue
// just finished non-last object value
93 scanEndObject
// end object (implies scanObjectValue if possible)
94 scanBeginArray
// begin array
95 scanArrayValue
// just finished array value
96 scanEndArray
// end array (implies scanArrayValue if possible)
97 scanSkipSpace
// space byte; can skip; known to be last "continue" result
100 scanEnd
// top-level value ended *before* this byte; known to be first "stop" result
101 scanError
// hit an error, scanner.err.
104 // These values are stored in the parseState stack.
105 // They give the current state of a composite value
106 // being scanned. If the parser is inside a nested value
107 // the parseState describes the nested state, outermost at entry 0.
109 parseObjectKey
= iota // parsing object key (before colon)
110 parseObjectValue
// parsing object value (after colon)
111 parseArrayValue
// parsing array value
114 // reset prepares the scanner for use.
115 // It must be called before calling s.step.
116 func (s
*scanner
) reset() {
117 s
.step
= stateBeginValue
118 s
.parseState
= s
.parseState
[0:0]
123 // eof tells the scanner that the end of input has been reached.
124 // It returns a scan status just as s.step does.
125 func (s
*scanner
) eof() int {
137 s
.err
= &SyntaxError
{"unexpected end of JSON input", s
.bytes
}
142 // pushParseState pushes a new parse state p onto the parse stack.
143 func (s
*scanner
) pushParseState(p
int) {
144 s
.parseState
= append(s
.parseState
, p
)
147 // popParseState pops a parse state (already obtained) off the stack
148 // and updates s.step accordingly.
149 func (s
*scanner
) popParseState() {
150 n
:= len(s
.parseState
) - 1
151 s
.parseState
= s
.parseState
[0:n
]
156 s
.step
= stateEndValue
160 func isSpace(c
byte) bool {
161 return c
== ' ' || c
== '\t' || c
== '\r' || c
== '\n'
164 // stateBeginValueOrEmpty is the state after reading `[`.
165 func stateBeginValueOrEmpty(s
*scanner
, c
byte) int {
166 if c
<= ' ' && isSpace(c
) {
170 return stateEndValue(s
, c
)
172 return stateBeginValue(s
, c
)
175 // stateBeginValue is the state at the beginning of the input.
176 func stateBeginValue(s
*scanner
, c
byte) int {
177 if c
<= ' ' && isSpace(c
) {
182 s
.step
= stateBeginStringOrEmpty
183 s
.pushParseState(parseObjectKey
)
184 return scanBeginObject
186 s
.step
= stateBeginValueOrEmpty
187 s
.pushParseState(parseArrayValue
)
188 return scanBeginArray
190 s
.step
= stateInString
191 return scanBeginLiteral
194 return scanBeginLiteral
195 case '0': // beginning of 0.123
197 return scanBeginLiteral
198 case 't': // beginning of true
200 return scanBeginLiteral
201 case 'f': // beginning of false
203 return scanBeginLiteral
204 case 'n': // beginning of null
206 return scanBeginLiteral
208 if '1' <= c
&& c
<= '9' { // beginning of 1234.5
210 return scanBeginLiteral
212 return s
.error(c
, "looking for beginning of value")
215 // stateBeginStringOrEmpty is the state after reading `{`.
216 func stateBeginStringOrEmpty(s
*scanner
, c
byte) int {
217 if c
<= ' ' && isSpace(c
) {
221 n
:= len(s
.parseState
)
222 s
.parseState
[n
-1] = parseObjectValue
223 return stateEndValue(s
, c
)
225 return stateBeginString(s
, c
)
228 // stateBeginString is the state after reading `{"key": value,`.
229 func stateBeginString(s
*scanner
, c
byte) int {
230 if c
<= ' ' && isSpace(c
) {
234 s
.step
= stateInString
235 return scanBeginLiteral
237 return s
.error(c
, "looking for beginning of object key string")
240 // stateEndValue is the state after completing a value,
241 // such as after reading `{}` or `true` or `["x"`.
242 func stateEndValue(s
*scanner
, c
byte) int {
243 n
:= len(s
.parseState
)
245 // Completed top-level before the current byte.
248 return stateEndTop(s
, c
)
250 if c
<= ' ' && isSpace(c
) {
251 s
.step
= stateEndValue
254 ps
:= s
.parseState
[n
-1]
258 s
.parseState
[n
-1] = parseObjectValue
259 s
.step
= stateBeginValue
262 return s
.error(c
, "after object key")
263 case parseObjectValue
:
265 s
.parseState
[n
-1] = parseObjectKey
266 s
.step
= stateBeginString
267 return scanObjectValue
273 return s
.error(c
, "after object key:value pair")
274 case parseArrayValue
:
276 s
.step
= stateBeginValue
277 return scanArrayValue
283 return s
.error(c
, "after array element")
285 return s
.error(c
, "")
288 // stateEndTop is the state after finishing the top-level value,
289 // such as after reading `{}` or `[1,2,3]`.
290 // Only space characters should be seen now.
291 func stateEndTop(s
*scanner
, c
byte) int {
292 if c
!= ' ' && c
!= '\t' && c
!= '\r' && c
!= '\n' {
293 // Complain about non-space byte on next call.
294 s
.error(c
, "after top-level value")
299 // stateInString is the state after reading `"`.
300 func stateInString(s
*scanner
, c
byte) int {
302 s
.step
= stateEndValue
306 s
.step
= stateInStringEsc
310 return s
.error(c
, "in string literal")
315 // stateInStringEsc is the state after reading `"\` during a quoted string.
316 func stateInStringEsc(s
*scanner
, c
byte) int {
318 case 'b', 'f', 'n', 'r', 't', '\\', '/', '"':
319 s
.step
= stateInString
322 s
.step
= stateInStringEscU
325 return s
.error(c
, "in string escape code")
328 // stateInStringEscU is the state after reading `"\u` during a quoted string.
329 func stateInStringEscU(s
*scanner
, c
byte) int {
330 if '0' <= c
&& c
<= '9' ||
'a' <= c
&& c
<= 'f' ||
'A' <= c
&& c
<= 'F' {
331 s
.step
= stateInStringEscU1
335 return s
.error(c
, "in \\u hexadecimal character escape")
338 // stateInStringEscU1 is the state after reading `"\u1` during a quoted string.
339 func stateInStringEscU1(s
*scanner
, c
byte) int {
340 if '0' <= c
&& c
<= '9' ||
'a' <= c
&& c
<= 'f' ||
'A' <= c
&& c
<= 'F' {
341 s
.step
= stateInStringEscU12
345 return s
.error(c
, "in \\u hexadecimal character escape")
348 // stateInStringEscU12 is the state after reading `"\u12` during a quoted string.
349 func stateInStringEscU12(s
*scanner
, c
byte) int {
350 if '0' <= c
&& c
<= '9' ||
'a' <= c
&& c
<= 'f' ||
'A' <= c
&& c
<= 'F' {
351 s
.step
= stateInStringEscU123
355 return s
.error(c
, "in \\u hexadecimal character escape")
358 // stateInStringEscU123 is the state after reading `"\u123` during a quoted string.
359 func stateInStringEscU123(s
*scanner
, c
byte) int {
360 if '0' <= c
&& c
<= '9' ||
'a' <= c
&& c
<= 'f' ||
'A' <= c
&& c
<= 'F' {
361 s
.step
= stateInString
365 return s
.error(c
, "in \\u hexadecimal character escape")
368 // stateNeg is the state after reading `-` during a number.
369 func stateNeg(s
*scanner
, c
byte) int {
374 if '1' <= c
&& c
<= '9' {
378 return s
.error(c
, "in numeric literal")
381 // state1 is the state after reading a non-zero integer during a number,
382 // such as after reading `1` or `100` but not `0`.
383 func state1(s
*scanner
, c
byte) int {
384 if '0' <= c
&& c
<= '9' {
391 // state0 is the state after reading `0` during a number.
392 func state0(s
*scanner
, c
byte) int {
397 if c
== 'e' || c
== 'E' {
401 return stateEndValue(s
, c
)
404 // stateDot is the state after reading the integer and decimal point in a number,
405 // such as after reading `1.`.
406 func stateDot(s
*scanner
, c
byte) int {
407 if '0' <= c
&& c
<= '9' {
411 return s
.error(c
, "after decimal point in numeric literal")
414 // stateDot0 is the state after reading the integer, decimal point, and subsequent
415 // digits of a number, such as after reading `3.14`.
416 func stateDot0(s
*scanner
, c
byte) int {
417 if '0' <= c
&& c
<= '9' {
420 if c
== 'e' || c
== 'E' {
424 return stateEndValue(s
, c
)
427 // stateE is the state after reading the mantissa and e in a number,
428 // such as after reading `314e` or `0.314e`.
429 func stateE(s
*scanner
, c
byte) int {
430 if c
== '+' || c
== '-' {
434 return stateESign(s
, c
)
437 // stateESign is the state after reading the mantissa, e, and sign in a number,
438 // such as after reading `314e-` or `0.314e+`.
439 func stateESign(s
*scanner
, c
byte) int {
440 if '0' <= c
&& c
<= '9' {
444 return s
.error(c
, "in exponent of numeric literal")
447 // stateE0 is the state after reading the mantissa, e, optional sign,
448 // and at least one digit of the exponent in a number,
449 // such as after reading `314e-2` or `0.314e+1` or `3.14e0`.
450 func stateE0(s
*scanner
, c
byte) int {
451 if '0' <= c
&& c
<= '9' {
454 return stateEndValue(s
, c
)
457 // stateT is the state after reading `t`.
458 func stateT(s
*scanner
, c
byte) int {
463 return s
.error(c
, "in literal true (expecting 'r')")
466 // stateTr is the state after reading `tr`.
467 func stateTr(s
*scanner
, c
byte) int {
472 return s
.error(c
, "in literal true (expecting 'u')")
475 // stateTru is the state after reading `tru`.
476 func stateTru(s
*scanner
, c
byte) int {
478 s
.step
= stateEndValue
481 return s
.error(c
, "in literal true (expecting 'e')")
484 // stateF is the state after reading `f`.
485 func stateF(s
*scanner
, c
byte) int {
490 return s
.error(c
, "in literal false (expecting 'a')")
493 // stateFa is the state after reading `fa`.
494 func stateFa(s
*scanner
, c
byte) int {
499 return s
.error(c
, "in literal false (expecting 'l')")
502 // stateFal is the state after reading `fal`.
503 func stateFal(s
*scanner
, c
byte) int {
508 return s
.error(c
, "in literal false (expecting 's')")
511 // stateFals is the state after reading `fals`.
512 func stateFals(s
*scanner
, c
byte) int {
514 s
.step
= stateEndValue
517 return s
.error(c
, "in literal false (expecting 'e')")
520 // stateN is the state after reading `n`.
521 func stateN(s
*scanner
, c
byte) int {
526 return s
.error(c
, "in literal null (expecting 'u')")
529 // stateNu is the state after reading `nu`.
530 func stateNu(s
*scanner
, c
byte) int {
535 return s
.error(c
, "in literal null (expecting 'l')")
538 // stateNul is the state after reading `nul`.
539 func stateNul(s
*scanner
, c
byte) int {
541 s
.step
= stateEndValue
544 return s
.error(c
, "in literal null (expecting 'l')")
547 // stateError is the state after reaching a syntax error,
548 // such as after reading `[1}` or `5.1.2`.
549 func stateError(s
*scanner
, c
byte) int {
553 // error records an error and switches to the error state.
554 func (s
*scanner
) error(c
byte, context
string) int {
556 s
.err
= &SyntaxError
{"invalid character " + quoteChar(c
) + " " + context
, s
.bytes
}
560 // quoteChar formats c as a quoted character literal
561 func quoteChar(c
byte) string {
562 // special cases - different from quoted strings
570 // use quoted string with different quotation marks
571 s
:= strconv
.Quote(string(c
))
572 return "'" + s
[1:len(s
)-1] + "'"