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.
21 // Valid reports whether data is a valid JSON encoding.
22 func Valid(data
[]byte) bool {
24 defer freeScanner(scan
)
25 return checkValid(data
, scan
) == nil
28 // checkValid verifies that data is valid JSON-encoded data.
29 // scan is passed in for use by checkValid to avoid an allocation.
30 func checkValid(data
[]byte, scan
*scanner
) error
{
32 for _
, c
:= range data
{
34 if scan
.step(scan
, c
) == scanError
{
38 if scan
.eof() == scanError
{
44 // A SyntaxError is a description of a JSON syntax error.
45 type SyntaxError
struct {
46 msg
string // description of error
47 Offset
int64 // error occurred after reading Offset bytes
50 func (e
*SyntaxError
) Error() string { return e
.msg
}
52 // A scanner is a JSON scanning state machine.
53 // Callers call scan.reset and then pass bytes in one at a time
54 // by calling scan.step(&scan, c) for each byte.
55 // The return value, referred to as an opcode, tells the
56 // caller about significant parsing events like beginning
57 // and ending literals, objects, and arrays, so that the
58 // caller can follow along if it wishes.
59 // The return value scanEnd indicates that a single top-level
60 // JSON value has been completed, *before* the byte that
61 // just got passed in. (The indication must be delayed in order
62 // to recognize the end of numbers: is 123 a whole value or
63 // the beginning of 12345e+6?).
65 // The step is a func to be called to execute the next transition.
66 // Also tried using an integer constant and a single func
67 // with a switch, but using the func directly was 10% faster
68 // on a 64-bit Mac Mini, and it's nicer to read.
69 step
func(*scanner
, byte) int
71 // Reached end of top-level value.
74 // Stack of what we're in the middle of - array values, object keys, object values.
77 // Error that happened, if any.
80 // total bytes consumed, updated by decoder.Decode (and deliberately
81 // not set to zero by scan.reset)
85 var scannerPool
= sync
.Pool
{
91 func newScanner() *scanner
{
92 scan
:= scannerPool
.Get().(*scanner
)
93 // scan.reset by design doesn't set bytes to zero
99 func freeScanner(scan
*scanner
) {
100 // Avoid hanging on to too much memory in extreme cases.
101 if len(scan
.parseState
) > 1024 {
102 scan
.parseState
= nil
104 scannerPool
.Put(scan
)
107 // These values are returned by the state transition functions
108 // assigned to scanner.state and the method scanner.eof.
109 // They give details about the current state of the scan that
110 // callers might be interested to know about.
111 // It is okay to ignore the return value of any particular
112 // call to scanner.state: if one call returns scanError,
113 // every subsequent call will return scanError too.
116 scanContinue
= iota // uninteresting byte
117 scanBeginLiteral
// end implied by next result != scanContinue
118 scanBeginObject
// begin object
119 scanObjectKey
// just finished object key (string)
120 scanObjectValue
// just finished non-last object value
121 scanEndObject
// end object (implies scanObjectValue if possible)
122 scanBeginArray
// begin array
123 scanArrayValue
// just finished array value
124 scanEndArray
// end array (implies scanArrayValue if possible)
125 scanSkipSpace
// space byte; can skip; known to be last "continue" result
128 scanEnd
// top-level value ended *before* this byte; known to be first "stop" result
129 scanError
// hit an error, scanner.err.
132 // These values are stored in the parseState stack.
133 // They give the current state of a composite value
134 // being scanned. If the parser is inside a nested value
135 // the parseState describes the nested state, outermost at entry 0.
137 parseObjectKey
= iota // parsing object key (before colon)
138 parseObjectValue
// parsing object value (after colon)
139 parseArrayValue
// parsing array value
142 // This limits the max nesting depth to prevent stack overflow.
143 // This is permitted by https://tools.ietf.org/html/rfc7159#section-9
144 const maxNestingDepth
= 10000
146 // reset prepares the scanner for use.
147 // It must be called before calling s.step.
148 func (s
*scanner
) reset() {
149 s
.step
= stateBeginValue
150 s
.parseState
= s
.parseState
[0:0]
155 // eof tells the scanner that the end of input has been reached.
156 // It returns a scan status just as s.step does.
157 func (s
*scanner
) eof() int {
169 s
.err
= &SyntaxError
{"unexpected end of JSON input", s
.bytes
}
174 // pushParseState pushes a new parse state p onto the parse stack.
175 // an error state is returned if maxNestingDepth was exceeded, otherwise successState is returned.
176 func (s
*scanner
) pushParseState(c
byte, newParseState
int, successState
int) int {
177 s
.parseState
= append(s
.parseState
, newParseState
)
178 if len(s
.parseState
) <= maxNestingDepth
{
181 return s
.error(c
, "exceeded max depth")
184 // popParseState pops a parse state (already obtained) off the stack
185 // and updates s.step accordingly.
186 func (s
*scanner
) popParseState() {
187 n
:= len(s
.parseState
) - 1
188 s
.parseState
= s
.parseState
[0:n
]
193 s
.step
= stateEndValue
197 func isSpace(c
byte) bool {
198 return c
<= ' ' && (c
== ' ' || c
== '\t' || c
== '\r' || c
== '\n')
201 // stateBeginValueOrEmpty is the state after reading `[`.
202 func stateBeginValueOrEmpty(s
*scanner
, c
byte) int {
207 return stateEndValue(s
, c
)
209 return stateBeginValue(s
, c
)
212 // stateBeginValue is the state at the beginning of the input.
213 func stateBeginValue(s
*scanner
, c
byte) int {
219 s
.step
= stateBeginStringOrEmpty
220 return s
.pushParseState(c
, parseObjectKey
, scanBeginObject
)
222 s
.step
= stateBeginValueOrEmpty
223 return s
.pushParseState(c
, parseArrayValue
, scanBeginArray
)
225 s
.step
= stateInString
226 return scanBeginLiteral
229 return scanBeginLiteral
230 case '0': // beginning of 0.123
232 return scanBeginLiteral
233 case 't': // beginning of true
235 return scanBeginLiteral
236 case 'f': // beginning of false
238 return scanBeginLiteral
239 case 'n': // beginning of null
241 return scanBeginLiteral
243 if '1' <= c
&& c
<= '9' { // beginning of 1234.5
245 return scanBeginLiteral
247 return s
.error(c
, "looking for beginning of value")
250 // stateBeginStringOrEmpty is the state after reading `{`.
251 func stateBeginStringOrEmpty(s
*scanner
, c
byte) int {
256 n
:= len(s
.parseState
)
257 s
.parseState
[n
-1] = parseObjectValue
258 return stateEndValue(s
, c
)
260 return stateBeginString(s
, c
)
263 // stateBeginString is the state after reading `{"key": value,`.
264 func stateBeginString(s
*scanner
, c
byte) int {
269 s
.step
= stateInString
270 return scanBeginLiteral
272 return s
.error(c
, "looking for beginning of object key string")
275 // stateEndValue is the state after completing a value,
276 // such as after reading `{}` or `true` or `["x"`.
277 func stateEndValue(s
*scanner
, c
byte) int {
278 n
:= len(s
.parseState
)
280 // Completed top-level before the current byte.
283 return stateEndTop(s
, c
)
286 s
.step
= stateEndValue
289 ps
:= s
.parseState
[n
-1]
293 s
.parseState
[n
-1] = parseObjectValue
294 s
.step
= stateBeginValue
297 return s
.error(c
, "after object key")
298 case parseObjectValue
:
300 s
.parseState
[n
-1] = parseObjectKey
301 s
.step
= stateBeginString
302 return scanObjectValue
308 return s
.error(c
, "after object key:value pair")
309 case parseArrayValue
:
311 s
.step
= stateBeginValue
312 return scanArrayValue
318 return s
.error(c
, "after array element")
320 return s
.error(c
, "")
323 // stateEndTop is the state after finishing the top-level value,
324 // such as after reading `{}` or `[1,2,3]`.
325 // Only space characters should be seen now.
326 func stateEndTop(s
*scanner
, c
byte) int {
328 // Complain about non-space byte on next call.
329 s
.error(c
, "after top-level value")
334 // stateInString is the state after reading `"`.
335 func stateInString(s
*scanner
, c
byte) int {
337 s
.step
= stateEndValue
341 s
.step
= stateInStringEsc
345 return s
.error(c
, "in string literal")
350 // stateInStringEsc is the state after reading `"\` during a quoted string.
351 func stateInStringEsc(s
*scanner
, c
byte) int {
353 case 'b', 'f', 'n', 'r', 't', '\\', '/', '"':
354 s
.step
= stateInString
357 s
.step
= stateInStringEscU
360 return s
.error(c
, "in string escape code")
363 // stateInStringEscU is the state after reading `"\u` during a quoted string.
364 func stateInStringEscU(s
*scanner
, c
byte) int {
365 if '0' <= c
&& c
<= '9' ||
'a' <= c
&& c
<= 'f' ||
'A' <= c
&& c
<= 'F' {
366 s
.step
= stateInStringEscU1
370 return s
.error(c
, "in \\u hexadecimal character escape")
373 // stateInStringEscU1 is the state after reading `"\u1` during a quoted string.
374 func stateInStringEscU1(s
*scanner
, c
byte) int {
375 if '0' <= c
&& c
<= '9' ||
'a' <= c
&& c
<= 'f' ||
'A' <= c
&& c
<= 'F' {
376 s
.step
= stateInStringEscU12
380 return s
.error(c
, "in \\u hexadecimal character escape")
383 // stateInStringEscU12 is the state after reading `"\u12` during a quoted string.
384 func stateInStringEscU12(s
*scanner
, c
byte) int {
385 if '0' <= c
&& c
<= '9' ||
'a' <= c
&& c
<= 'f' ||
'A' <= c
&& c
<= 'F' {
386 s
.step
= stateInStringEscU123
390 return s
.error(c
, "in \\u hexadecimal character escape")
393 // stateInStringEscU123 is the state after reading `"\u123` during a quoted string.
394 func stateInStringEscU123(s
*scanner
, c
byte) int {
395 if '0' <= c
&& c
<= '9' ||
'a' <= c
&& c
<= 'f' ||
'A' <= c
&& c
<= 'F' {
396 s
.step
= stateInString
400 return s
.error(c
, "in \\u hexadecimal character escape")
403 // stateNeg is the state after reading `-` during a number.
404 func stateNeg(s
*scanner
, c
byte) int {
409 if '1' <= c
&& c
<= '9' {
413 return s
.error(c
, "in numeric literal")
416 // state1 is the state after reading a non-zero integer during a number,
417 // such as after reading `1` or `100` but not `0`.
418 func state1(s
*scanner
, c
byte) int {
419 if '0' <= c
&& c
<= '9' {
426 // state0 is the state after reading `0` during a number.
427 func state0(s
*scanner
, c
byte) int {
432 if c
== 'e' || c
== 'E' {
436 return stateEndValue(s
, c
)
439 // stateDot is the state after reading the integer and decimal point in a number,
440 // such as after reading `1.`.
441 func stateDot(s
*scanner
, c
byte) int {
442 if '0' <= c
&& c
<= '9' {
446 return s
.error(c
, "after decimal point in numeric literal")
449 // stateDot0 is the state after reading the integer, decimal point, and subsequent
450 // digits of a number, such as after reading `3.14`.
451 func stateDot0(s
*scanner
, c
byte) int {
452 if '0' <= c
&& c
<= '9' {
455 if c
== 'e' || c
== 'E' {
459 return stateEndValue(s
, c
)
462 // stateE is the state after reading the mantissa and e in a number,
463 // such as after reading `314e` or `0.314e`.
464 func stateE(s
*scanner
, c
byte) int {
465 if c
== '+' || c
== '-' {
469 return stateESign(s
, c
)
472 // stateESign is the state after reading the mantissa, e, and sign in a number,
473 // such as after reading `314e-` or `0.314e+`.
474 func stateESign(s
*scanner
, c
byte) int {
475 if '0' <= c
&& c
<= '9' {
479 return s
.error(c
, "in exponent of numeric literal")
482 // stateE0 is the state after reading the mantissa, e, optional sign,
483 // and at least one digit of the exponent in a number,
484 // such as after reading `314e-2` or `0.314e+1` or `3.14e0`.
485 func stateE0(s
*scanner
, c
byte) int {
486 if '0' <= c
&& c
<= '9' {
489 return stateEndValue(s
, c
)
492 // stateT is the state after reading `t`.
493 func stateT(s
*scanner
, c
byte) int {
498 return s
.error(c
, "in literal true (expecting 'r')")
501 // stateTr is the state after reading `tr`.
502 func stateTr(s
*scanner
, c
byte) int {
507 return s
.error(c
, "in literal true (expecting 'u')")
510 // stateTru is the state after reading `tru`.
511 func stateTru(s
*scanner
, c
byte) int {
513 s
.step
= stateEndValue
516 return s
.error(c
, "in literal true (expecting 'e')")
519 // stateF is the state after reading `f`.
520 func stateF(s
*scanner
, c
byte) int {
525 return s
.error(c
, "in literal false (expecting 'a')")
528 // stateFa is the state after reading `fa`.
529 func stateFa(s
*scanner
, c
byte) int {
534 return s
.error(c
, "in literal false (expecting 'l')")
537 // stateFal is the state after reading `fal`.
538 func stateFal(s
*scanner
, c
byte) int {
543 return s
.error(c
, "in literal false (expecting 's')")
546 // stateFals is the state after reading `fals`.
547 func stateFals(s
*scanner
, c
byte) int {
549 s
.step
= stateEndValue
552 return s
.error(c
, "in literal false (expecting 'e')")
555 // stateN is the state after reading `n`.
556 func stateN(s
*scanner
, c
byte) int {
561 return s
.error(c
, "in literal null (expecting 'u')")
564 // stateNu is the state after reading `nu`.
565 func stateNu(s
*scanner
, c
byte) int {
570 return s
.error(c
, "in literal null (expecting 'l')")
573 // stateNul is the state after reading `nul`.
574 func stateNul(s
*scanner
, c
byte) int {
576 s
.step
= stateEndValue
579 return s
.error(c
, "in literal null (expecting 'l')")
582 // stateError is the state after reaching a syntax error,
583 // such as after reading `[1}` or `5.1.2`.
584 func stateError(s
*scanner
, c
byte) int {
588 // error records an error and switches to the error state.
589 func (s
*scanner
) error(c
byte, context
string) int {
591 s
.err
= &SyntaxError
{"invalid character " + quoteChar(c
) + " " + context
, s
.bytes
}
595 // quoteChar formats c as a quoted character literal
596 func quoteChar(c
byte) string {
597 // special cases - different from quoted strings
605 // use quoted string with different quotation marks
606 s
:= strconv
.Quote(string(c
))
607 return "'" + s
[1:len(s
)-1] + "'"