Source file src/encoding/json/scanner.go

     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.
     4	
     5	package json
     6	
     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).
    12	//
    13	// This file starts with two simple examples using the scanner
    14	// before diving into the scanner itself.
    15	
    16	import "strconv"
    17	
    18	// Valid reports whether data is a valid JSON encoding.
    19	func Valid(data []byte) bool {
    20		return checkValid(data, &scanner{}) == nil
    21	}
    22	
    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 {
    26		scan.reset()
    27		for _, c := range data {
    28			scan.bytes++
    29			if scan.step(scan, c) == scanError {
    30				return scan.err
    31			}
    32		}
    33		if scan.eof() == scanError {
    34			return scan.err
    35		}
    36		return nil
    37	}
    38	
    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
    43	}
    44	
    45	func (e *SyntaxError) Error() string { return e.msg }
    46	
    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?).
    59	type scanner struct {
    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
    65	
    66		// Reached end of top-level value.
    67		endTop bool
    68	
    69		// Stack of what we're in the middle of - array values, object keys, object values.
    70		parseState []int
    71	
    72		// Error that happened, if any.
    73		err error
    74	
    75		// total bytes consumed, updated by decoder.Decode
    76		bytes int64
    77	}
    78	
    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.
    86	const (
    87		// Continue.
    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
    98	
    99		// Stop.
   100		scanEnd   // top-level value ended *before* this byte; known to be first "stop" result
   101		scanError // hit an error, scanner.err.
   102	)
   103	
   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.
   108	const (
   109		parseObjectKey   = iota // parsing object key (before colon)
   110		parseObjectValue        // parsing object value (after colon)
   111		parseArrayValue         // parsing array value
   112	)
   113	
   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]
   119		s.err = nil
   120		s.endTop = false
   121	}
   122	
   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 {
   126		if s.err != nil {
   127			return scanError
   128		}
   129		if s.endTop {
   130			return scanEnd
   131		}
   132		s.step(s, ' ')
   133		if s.endTop {
   134			return scanEnd
   135		}
   136		if s.err == nil {
   137			s.err = &SyntaxError{"unexpected end of JSON input", s.bytes}
   138		}
   139		return scanError
   140	}
   141	
   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)
   145	}
   146	
   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]
   152		if n == 0 {
   153			s.step = stateEndTop
   154			s.endTop = true
   155		} else {
   156			s.step = stateEndValue
   157		}
   158	}
   159	
   160	func isSpace(c byte) bool {
   161		return c == ' ' || c == '\t' || c == '\r' || c == '\n'
   162	}
   163	
   164	// stateBeginValueOrEmpty is the state after reading `[`.
   165	func stateBeginValueOrEmpty(s *scanner, c byte) int {
   166		if c <= ' ' && isSpace(c) {
   167			return scanSkipSpace
   168		}
   169		if c == ']' {
   170			return stateEndValue(s, c)
   171		}
   172		return stateBeginValue(s, c)
   173	}
   174	
   175	// stateBeginValue is the state at the beginning of the input.
   176	func stateBeginValue(s *scanner, c byte) int {
   177		if c <= ' ' && isSpace(c) {
   178			return scanSkipSpace
   179		}
   180		switch c {
   181		case '{':
   182			s.step = stateBeginStringOrEmpty
   183			s.pushParseState(parseObjectKey)
   184			return scanBeginObject
   185		case '[':
   186			s.step = stateBeginValueOrEmpty
   187			s.pushParseState(parseArrayValue)
   188			return scanBeginArray
   189		case '"':
   190			s.step = stateInString
   191			return scanBeginLiteral
   192		case '-':
   193			s.step = stateNeg
   194			return scanBeginLiteral
   195		case '0': // beginning of 0.123
   196			s.step = state0
   197			return scanBeginLiteral
   198		case 't': // beginning of true
   199			s.step = stateT
   200			return scanBeginLiteral
   201		case 'f': // beginning of false
   202			s.step = stateF
   203			return scanBeginLiteral
   204		case 'n': // beginning of null
   205			s.step = stateN
   206			return scanBeginLiteral
   207		}
   208		if '1' <= c && c <= '9' { // beginning of 1234.5
   209			s.step = state1
   210			return scanBeginLiteral
   211		}
   212		return s.error(c, "looking for beginning of value")
   213	}
   214	
   215	// stateBeginStringOrEmpty is the state after reading `{`.
   216	func stateBeginStringOrEmpty(s *scanner, c byte) int {
   217		if c <= ' ' && isSpace(c) {
   218			return scanSkipSpace
   219		}
   220		if c == '}' {
   221			n := len(s.parseState)
   222			s.parseState[n-1] = parseObjectValue
   223			return stateEndValue(s, c)
   224		}
   225		return stateBeginString(s, c)
   226	}
   227	
   228	// stateBeginString is the state after reading `{"key": value,`.
   229	func stateBeginString(s *scanner, c byte) int {
   230		if c <= ' ' && isSpace(c) {
   231			return scanSkipSpace
   232		}
   233		if c == '"' {
   234			s.step = stateInString
   235			return scanBeginLiteral
   236		}
   237		return s.error(c, "looking for beginning of object key string")
   238	}
   239	
   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)
   244		if n == 0 {
   245			// Completed top-level before the current byte.
   246			s.step = stateEndTop
   247			s.endTop = true
   248			return stateEndTop(s, c)
   249		}
   250		if c <= ' ' && isSpace(c) {
   251			s.step = stateEndValue
   252			return scanSkipSpace
   253		}
   254		ps := s.parseState[n-1]
   255		switch ps {
   256		case parseObjectKey:
   257			if c == ':' {
   258				s.parseState[n-1] = parseObjectValue
   259				s.step = stateBeginValue
   260				return scanObjectKey
   261			}
   262			return s.error(c, "after object key")
   263		case parseObjectValue:
   264			if c == ',' {
   265				s.parseState[n-1] = parseObjectKey
   266				s.step = stateBeginString
   267				return scanObjectValue
   268			}
   269			if c == '}' {
   270				s.popParseState()
   271				return scanEndObject
   272			}
   273			return s.error(c, "after object key:value pair")
   274		case parseArrayValue:
   275			if c == ',' {
   276				s.step = stateBeginValue
   277				return scanArrayValue
   278			}
   279			if c == ']' {
   280				s.popParseState()
   281				return scanEndArray
   282			}
   283			return s.error(c, "after array element")
   284		}
   285		return s.error(c, "")
   286	}
   287	
   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 !isSpace(c) {
   293			// Complain about non-space byte on next call.
   294			s.error(c, "after top-level value")
   295		}
   296		return scanEnd
   297	}
   298	
   299	// stateInString is the state after reading `"`.
   300	func stateInString(s *scanner, c byte) int {
   301		if c == '"' {
   302			s.step = stateEndValue
   303			return scanContinue
   304		}
   305		if c == '\\' {
   306			s.step = stateInStringEsc
   307			return scanContinue
   308		}
   309		if c < 0x20 {
   310			return s.error(c, "in string literal")
   311		}
   312		return scanContinue
   313	}
   314	
   315	// stateInStringEsc is the state after reading `"\` during a quoted string.
   316	func stateInStringEsc(s *scanner, c byte) int {
   317		switch c {
   318		case 'b', 'f', 'n', 'r', 't', '\\', '/', '"':
   319			s.step = stateInString
   320			return scanContinue
   321		case 'u':
   322			s.step = stateInStringEscU
   323			return scanContinue
   324		}
   325		return s.error(c, "in string escape code")
   326	}
   327	
   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
   332			return scanContinue
   333		}
   334		// numbers
   335		return s.error(c, "in \\u hexadecimal character escape")
   336	}
   337	
   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
   342			return scanContinue
   343		}
   344		// numbers
   345		return s.error(c, "in \\u hexadecimal character escape")
   346	}
   347	
   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
   352			return scanContinue
   353		}
   354		// numbers
   355		return s.error(c, "in \\u hexadecimal character escape")
   356	}
   357	
   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
   362			return scanContinue
   363		}
   364		// numbers
   365		return s.error(c, "in \\u hexadecimal character escape")
   366	}
   367	
   368	// stateNeg is the state after reading `-` during a number.
   369	func stateNeg(s *scanner, c byte) int {
   370		if c == '0' {
   371			s.step = state0
   372			return scanContinue
   373		}
   374		if '1' <= c && c <= '9' {
   375			s.step = state1
   376			return scanContinue
   377		}
   378		return s.error(c, "in numeric literal")
   379	}
   380	
   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' {
   385			s.step = state1
   386			return scanContinue
   387		}
   388		return state0(s, c)
   389	}
   390	
   391	// state0 is the state after reading `0` during a number.
   392	func state0(s *scanner, c byte) int {
   393		if c == '.' {
   394			s.step = stateDot
   395			return scanContinue
   396		}
   397		if c == 'e' || c == 'E' {
   398			s.step = stateE
   399			return scanContinue
   400		}
   401		return stateEndValue(s, c)
   402	}
   403	
   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' {
   408			s.step = stateDot0
   409			return scanContinue
   410		}
   411		return s.error(c, "after decimal point in numeric literal")
   412	}
   413	
   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' {
   418			return scanContinue
   419		}
   420		if c == 'e' || c == 'E' {
   421			s.step = stateE
   422			return scanContinue
   423		}
   424		return stateEndValue(s, c)
   425	}
   426	
   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 == '-' {
   431			s.step = stateESign
   432			return scanContinue
   433		}
   434		return stateESign(s, c)
   435	}
   436	
   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' {
   441			s.step = stateE0
   442			return scanContinue
   443		}
   444		return s.error(c, "in exponent of numeric literal")
   445	}
   446	
   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' {
   452			return scanContinue
   453		}
   454		return stateEndValue(s, c)
   455	}
   456	
   457	// stateT is the state after reading `t`.
   458	func stateT(s *scanner, c byte) int {
   459		if c == 'r' {
   460			s.step = stateTr
   461			return scanContinue
   462		}
   463		return s.error(c, "in literal true (expecting 'r')")
   464	}
   465	
   466	// stateTr is the state after reading `tr`.
   467	func stateTr(s *scanner, c byte) int {
   468		if c == 'u' {
   469			s.step = stateTru
   470			return scanContinue
   471		}
   472		return s.error(c, "in literal true (expecting 'u')")
   473	}
   474	
   475	// stateTru is the state after reading `tru`.
   476	func stateTru(s *scanner, c byte) int {
   477		if c == 'e' {
   478			s.step = stateEndValue
   479			return scanContinue
   480		}
   481		return s.error(c, "in literal true (expecting 'e')")
   482	}
   483	
   484	// stateF is the state after reading `f`.
   485	func stateF(s *scanner, c byte) int {
   486		if c == 'a' {
   487			s.step = stateFa
   488			return scanContinue
   489		}
   490		return s.error(c, "in literal false (expecting 'a')")
   491	}
   492	
   493	// stateFa is the state after reading `fa`.
   494	func stateFa(s *scanner, c byte) int {
   495		if c == 'l' {
   496			s.step = stateFal
   497			return scanContinue
   498		}
   499		return s.error(c, "in literal false (expecting 'l')")
   500	}
   501	
   502	// stateFal is the state after reading `fal`.
   503	func stateFal(s *scanner, c byte) int {
   504		if c == 's' {
   505			s.step = stateFals
   506			return scanContinue
   507		}
   508		return s.error(c, "in literal false (expecting 's')")
   509	}
   510	
   511	// stateFals is the state after reading `fals`.
   512	func stateFals(s *scanner, c byte) int {
   513		if c == 'e' {
   514			s.step = stateEndValue
   515			return scanContinue
   516		}
   517		return s.error(c, "in literal false (expecting 'e')")
   518	}
   519	
   520	// stateN is the state after reading `n`.
   521	func stateN(s *scanner, c byte) int {
   522		if c == 'u' {
   523			s.step = stateNu
   524			return scanContinue
   525		}
   526		return s.error(c, "in literal null (expecting 'u')")
   527	}
   528	
   529	// stateNu is the state after reading `nu`.
   530	func stateNu(s *scanner, c byte) int {
   531		if c == 'l' {
   532			s.step = stateNul
   533			return scanContinue
   534		}
   535		return s.error(c, "in literal null (expecting 'l')")
   536	}
   537	
   538	// stateNul is the state after reading `nul`.
   539	func stateNul(s *scanner, c byte) int {
   540		if c == 'l' {
   541			s.step = stateEndValue
   542			return scanContinue
   543		}
   544		return s.error(c, "in literal null (expecting 'l')")
   545	}
   546	
   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 {
   550		return scanError
   551	}
   552	
   553	// error records an error and switches to the error state.
   554	func (s *scanner) error(c byte, context string) int {
   555		s.step = stateError
   556		s.err = &SyntaxError{"invalid character " + quoteChar(c) + " " + context, s.bytes}
   557		return scanError
   558	}
   559	
   560	// quoteChar formats c as a quoted character literal
   561	func quoteChar(c byte) string {
   562		// special cases - different from quoted strings
   563		if c == '\'' {
   564			return `'\''`
   565		}
   566		if c == '"' {
   567			return `'"'`
   568		}
   569	
   570		// use quoted string with different quotation marks
   571		s := strconv.Quote(string(c))
   572		return "'" + s[1:len(s)-1] + "'"
   573	}
   574	

View as plain text