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 (
    17  	"strconv"
    18  	"sync"
    19  )
    20  
    21  // Valid reports whether data is a valid JSON encoding.
    22  func Valid(data []byte) bool {
    23  	scan := newScanner()
    24  	defer freeScanner(scan)
    25  	return checkValid(data, scan) == nil
    26  }
    27  
    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 {
    31  	scan.reset()
    32  	for _, c := range data {
    33  		scan.bytes++
    34  		if scan.step(scan, c) == scanError {
    35  			return scan.err
    36  		}
    37  	}
    38  	if scan.eof() == scanError {
    39  		return scan.err
    40  	}
    41  	return nil
    42  }
    43  
    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
    48  }
    49  
    50  func (e *SyntaxError) Error() string { return e.msg }
    51  
    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?).
    64  type scanner struct {
    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
    70  
    71  	// Reached end of top-level value.
    72  	endTop bool
    73  
    74  	// Stack of what we're in the middle of - array values, object keys, object values.
    75  	parseState []int
    76  
    77  	// Error that happened, if any.
    78  	err error
    79  
    80  	// total bytes consumed, updated by decoder.Decode (and deliberately
    81  	// not set to zero by scan.reset)
    82  	bytes int64
    83  }
    84  
    85  var scannerPool = sync.Pool{
    86  	New: func() interface{} {
    87  		return &scanner{}
    88  	},
    89  }
    90  
    91  func newScanner() *scanner {
    92  	scan := scannerPool.Get().(*scanner)
    93  	// scan.reset by design doesn't set bytes to zero
    94  	scan.bytes = 0
    95  	scan.reset()
    96  	return scan
    97  }
    98  
    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
   103  	}
   104  	scannerPool.Put(scan)
   105  }
   106  
   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.
   114  const (
   115  	// Continue.
   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
   126  
   127  	// Stop.
   128  	scanEnd   // top-level value ended *before* this byte; known to be first "stop" result
   129  	scanError // hit an error, scanner.err.
   130  )
   131  
   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.
   136  const (
   137  	parseObjectKey   = iota // parsing object key (before colon)
   138  	parseObjectValue        // parsing object value (after colon)
   139  	parseArrayValue         // parsing array value
   140  )
   141  
   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
   145  
   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]
   151  	s.err = nil
   152  	s.endTop = false
   153  }
   154  
   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 {
   158  	if s.err != nil {
   159  		return scanError
   160  	}
   161  	if s.endTop {
   162  		return scanEnd
   163  	}
   164  	s.step(s, ' ')
   165  	if s.endTop {
   166  		return scanEnd
   167  	}
   168  	if s.err == nil {
   169  		s.err = &SyntaxError{"unexpected end of JSON input", s.bytes}
   170  	}
   171  	return scanError
   172  }
   173  
   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 {
   179  		return successState
   180  	}
   181  	return s.error(c, "exceeded max depth")
   182  }
   183  
   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]
   189  	if n == 0 {
   190  		s.step = stateEndTop
   191  		s.endTop = true
   192  	} else {
   193  		s.step = stateEndValue
   194  	}
   195  }
   196  
   197  func isSpace(c byte) bool {
   198  	return c <= ' ' && (c == ' ' || c == '\t' || c == '\r' || c == '\n')
   199  }
   200  
   201  // stateBeginValueOrEmpty is the state after reading `[`.
   202  func stateBeginValueOrEmpty(s *scanner, c byte) int {
   203  	if isSpace(c) {
   204  		return scanSkipSpace
   205  	}
   206  	if c == ']' {
   207  		return stateEndValue(s, c)
   208  	}
   209  	return stateBeginValue(s, c)
   210  }
   211  
   212  // stateBeginValue is the state at the beginning of the input.
   213  func stateBeginValue(s *scanner, c byte) int {
   214  	if isSpace(c) {
   215  		return scanSkipSpace
   216  	}
   217  	switch c {
   218  	case '{':
   219  		s.step = stateBeginStringOrEmpty
   220  		return s.pushParseState(c, parseObjectKey, scanBeginObject)
   221  	case '[':
   222  		s.step = stateBeginValueOrEmpty
   223  		return s.pushParseState(c, parseArrayValue, scanBeginArray)
   224  	case '"':
   225  		s.step = stateInString
   226  		return scanBeginLiteral
   227  	case '-':
   228  		s.step = stateNeg
   229  		return scanBeginLiteral
   230  	case '0': // beginning of 0.123
   231  		s.step = state0
   232  		return scanBeginLiteral
   233  	case 't': // beginning of true
   234  		s.step = stateT
   235  		return scanBeginLiteral
   236  	case 'f': // beginning of false
   237  		s.step = stateF
   238  		return scanBeginLiteral
   239  	case 'n': // beginning of null
   240  		s.step = stateN
   241  		return scanBeginLiteral
   242  	}
   243  	if '1' <= c && c <= '9' { // beginning of 1234.5
   244  		s.step = state1
   245  		return scanBeginLiteral
   246  	}
   247  	return s.error(c, "looking for beginning of value")
   248  }
   249  
   250  // stateBeginStringOrEmpty is the state after reading `{`.
   251  func stateBeginStringOrEmpty(s *scanner, c byte) int {
   252  	if isSpace(c) {
   253  		return scanSkipSpace
   254  	}
   255  	if c == '}' {
   256  		n := len(s.parseState)
   257  		s.parseState[n-1] = parseObjectValue
   258  		return stateEndValue(s, c)
   259  	}
   260  	return stateBeginString(s, c)
   261  }
   262  
   263  // stateBeginString is the state after reading `{"key": value,`.
   264  func stateBeginString(s *scanner, c byte) int {
   265  	if isSpace(c) {
   266  		return scanSkipSpace
   267  	}
   268  	if c == '"' {
   269  		s.step = stateInString
   270  		return scanBeginLiteral
   271  	}
   272  	return s.error(c, "looking for beginning of object key string")
   273  }
   274  
   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)
   279  	if n == 0 {
   280  		// Completed top-level before the current byte.
   281  		s.step = stateEndTop
   282  		s.endTop = true
   283  		return stateEndTop(s, c)
   284  	}
   285  	if isSpace(c) {
   286  		s.step = stateEndValue
   287  		return scanSkipSpace
   288  	}
   289  	ps := s.parseState[n-1]
   290  	switch ps {
   291  	case parseObjectKey:
   292  		if c == ':' {
   293  			s.parseState[n-1] = parseObjectValue
   294  			s.step = stateBeginValue
   295  			return scanObjectKey
   296  		}
   297  		return s.error(c, "after object key")
   298  	case parseObjectValue:
   299  		if c == ',' {
   300  			s.parseState[n-1] = parseObjectKey
   301  			s.step = stateBeginString
   302  			return scanObjectValue
   303  		}
   304  		if c == '}' {
   305  			s.popParseState()
   306  			return scanEndObject
   307  		}
   308  		return s.error(c, "after object key:value pair")
   309  	case parseArrayValue:
   310  		if c == ',' {
   311  			s.step = stateBeginValue
   312  			return scanArrayValue
   313  		}
   314  		if c == ']' {
   315  			s.popParseState()
   316  			return scanEndArray
   317  		}
   318  		return s.error(c, "after array element")
   319  	}
   320  	return s.error(c, "")
   321  }
   322  
   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 {
   327  	if !isSpace(c) {
   328  		// Complain about non-space byte on next call.
   329  		s.error(c, "after top-level value")
   330  	}
   331  	return scanEnd
   332  }
   333  
   334  // stateInString is the state after reading `"`.
   335  func stateInString(s *scanner, c byte) int {
   336  	if c == '"' {
   337  		s.step = stateEndValue
   338  		return scanContinue
   339  	}
   340  	if c == '\\' {
   341  		s.step = stateInStringEsc
   342  		return scanContinue
   343  	}
   344  	if c < 0x20 {
   345  		return s.error(c, "in string literal")
   346  	}
   347  	return scanContinue
   348  }
   349  
   350  // stateInStringEsc is the state after reading `"\` during a quoted string.
   351  func stateInStringEsc(s *scanner, c byte) int {
   352  	switch c {
   353  	case 'b', 'f', 'n', 'r', 't', '\\', '/', '"':
   354  		s.step = stateInString
   355  		return scanContinue
   356  	case 'u':
   357  		s.step = stateInStringEscU
   358  		return scanContinue
   359  	}
   360  	return s.error(c, "in string escape code")
   361  }
   362  
   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
   367  		return scanContinue
   368  	}
   369  	// numbers
   370  	return s.error(c, "in \\u hexadecimal character escape")
   371  }
   372  
   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
   377  		return scanContinue
   378  	}
   379  	// numbers
   380  	return s.error(c, "in \\u hexadecimal character escape")
   381  }
   382  
   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
   387  		return scanContinue
   388  	}
   389  	// numbers
   390  	return s.error(c, "in \\u hexadecimal character escape")
   391  }
   392  
   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
   397  		return scanContinue
   398  	}
   399  	// numbers
   400  	return s.error(c, "in \\u hexadecimal character escape")
   401  }
   402  
   403  // stateNeg is the state after reading `-` during a number.
   404  func stateNeg(s *scanner, c byte) int {
   405  	if c == '0' {
   406  		s.step = state0
   407  		return scanContinue
   408  	}
   409  	if '1' <= c && c <= '9' {
   410  		s.step = state1
   411  		return scanContinue
   412  	}
   413  	return s.error(c, "in numeric literal")
   414  }
   415  
   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' {
   420  		s.step = state1
   421  		return scanContinue
   422  	}
   423  	return state0(s, c)
   424  }
   425  
   426  // state0 is the state after reading `0` during a number.
   427  func state0(s *scanner, c byte) int {
   428  	if c == '.' {
   429  		s.step = stateDot
   430  		return scanContinue
   431  	}
   432  	if c == 'e' || c == 'E' {
   433  		s.step = stateE
   434  		return scanContinue
   435  	}
   436  	return stateEndValue(s, c)
   437  }
   438  
   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' {
   443  		s.step = stateDot0
   444  		return scanContinue
   445  	}
   446  	return s.error(c, "after decimal point in numeric literal")
   447  }
   448  
   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' {
   453  		return scanContinue
   454  	}
   455  	if c == 'e' || c == 'E' {
   456  		s.step = stateE
   457  		return scanContinue
   458  	}
   459  	return stateEndValue(s, c)
   460  }
   461  
   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 == '-' {
   466  		s.step = stateESign
   467  		return scanContinue
   468  	}
   469  	return stateESign(s, c)
   470  }
   471  
   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' {
   476  		s.step = stateE0
   477  		return scanContinue
   478  	}
   479  	return s.error(c, "in exponent of numeric literal")
   480  }
   481  
   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' {
   487  		return scanContinue
   488  	}
   489  	return stateEndValue(s, c)
   490  }
   491  
   492  // stateT is the state after reading `t`.
   493  func stateT(s *scanner, c byte) int {
   494  	if c == 'r' {
   495  		s.step = stateTr
   496  		return scanContinue
   497  	}
   498  	return s.error(c, "in literal true (expecting 'r')")
   499  }
   500  
   501  // stateTr is the state after reading `tr`.
   502  func stateTr(s *scanner, c byte) int {
   503  	if c == 'u' {
   504  		s.step = stateTru
   505  		return scanContinue
   506  	}
   507  	return s.error(c, "in literal true (expecting 'u')")
   508  }
   509  
   510  // stateTru is the state after reading `tru`.
   511  func stateTru(s *scanner, c byte) int {
   512  	if c == 'e' {
   513  		s.step = stateEndValue
   514  		return scanContinue
   515  	}
   516  	return s.error(c, "in literal true (expecting 'e')")
   517  }
   518  
   519  // stateF is the state after reading `f`.
   520  func stateF(s *scanner, c byte) int {
   521  	if c == 'a' {
   522  		s.step = stateFa
   523  		return scanContinue
   524  	}
   525  	return s.error(c, "in literal false (expecting 'a')")
   526  }
   527  
   528  // stateFa is the state after reading `fa`.
   529  func stateFa(s *scanner, c byte) int {
   530  	if c == 'l' {
   531  		s.step = stateFal
   532  		return scanContinue
   533  	}
   534  	return s.error(c, "in literal false (expecting 'l')")
   535  }
   536  
   537  // stateFal is the state after reading `fal`.
   538  func stateFal(s *scanner, c byte) int {
   539  	if c == 's' {
   540  		s.step = stateFals
   541  		return scanContinue
   542  	}
   543  	return s.error(c, "in literal false (expecting 's')")
   544  }
   545  
   546  // stateFals is the state after reading `fals`.
   547  func stateFals(s *scanner, c byte) int {
   548  	if c == 'e' {
   549  		s.step = stateEndValue
   550  		return scanContinue
   551  	}
   552  	return s.error(c, "in literal false (expecting 'e')")
   553  }
   554  
   555  // stateN is the state after reading `n`.
   556  func stateN(s *scanner, c byte) int {
   557  	if c == 'u' {
   558  		s.step = stateNu
   559  		return scanContinue
   560  	}
   561  	return s.error(c, "in literal null (expecting 'u')")
   562  }
   563  
   564  // stateNu is the state after reading `nu`.
   565  func stateNu(s *scanner, c byte) int {
   566  	if c == 'l' {
   567  		s.step = stateNul
   568  		return scanContinue
   569  	}
   570  	return s.error(c, "in literal null (expecting 'l')")
   571  }
   572  
   573  // stateNul is the state after reading `nul`.
   574  func stateNul(s *scanner, c byte) int {
   575  	if c == 'l' {
   576  		s.step = stateEndValue
   577  		return scanContinue
   578  	}
   579  	return s.error(c, "in literal null (expecting 'l')")
   580  }
   581  
   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 {
   585  	return scanError
   586  }
   587  
   588  // error records an error and switches to the error state.
   589  func (s *scanner) error(c byte, context string) int {
   590  	s.step = stateError
   591  	s.err = &SyntaxError{"invalid character " + quoteChar(c) + " " + context, s.bytes}
   592  	return scanError
   593  }
   594  
   595  // quoteChar formats c as a quoted character literal
   596  func quoteChar(c byte) string {
   597  	// special cases - different from quoted strings
   598  	if c == '\'' {
   599  		return `'\''`
   600  	}
   601  	if c == '"' {
   602  		return `'"'`
   603  	}
   604  
   605  	// use quoted string with different quotation marks
   606  	s := strconv.Quote(string(c))
   607  	return "'" + s[1:len(s)-1] + "'"
   608  }
   609  

View as plain text