json.go

Documentation: github.com/gabriel-vasile/mimetype/internal/json

     1  // Copyright (c) 2009 The Go Authors. All rights reserved.
     2  //
     3  // Redistribution and use in source and binary forms, with or without
     4  // modification, are permitted provided that the following conditions are
     5  // met:
     6  //
     7  //    * Redistributions of source code must retain the above copyright
     8  // notice, this list of conditions and the following disclaimer.
     9  //    * Redistributions in binary form must reproduce the above
    10  // copyright notice, this list of conditions and the following disclaimer
    11  // in the documentation and/or other materials provided with the
    12  // distribution.
    13  //    * Neither the name of Google Inc. nor the names of its
    14  // contributors may be used to endorse or promote products derived from
    15  // this software without specific prior written permission.
    16  //
    17  // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
    18  // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
    19  // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
    20  // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
    21  // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
    22  // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
    23  // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
    24  // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
    25  // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
    26  // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
    27  // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
    28  
    29  // Package json provides a JSON value parser state machine.
    30  // This package is almost entirely copied from the Go stdlib.
    31  // Changes made to it permit users of the package to tell
    32  // if some slice of bytes is a valid beginning of a json string.
    33  package json
    34  
    35  import (
    36  	"fmt"
    37  )
    38  
    39  type (
    40  	scanStatus int
    41  )
    42  
    43  const (
    44  	parseObjectKey   = iota // parsing object key (before colon)
    45  	parseObjectValue        // parsing object value (after colon)
    46  	parseArrayValue         // parsing array value
    47  
    48  	scanContinue     scanStatus = iota // uninteresting byte
    49  	scanBeginLiteral                   // end implied by next result != scanContinue
    50  	scanBeginObject                    // begin object
    51  	scanObjectKey                      // just finished object key (string)
    52  	scanObjectValue                    // just finished non-last object value
    53  	scanEndObject                      // end object (implies scanObjectValue if possible)
    54  	scanBeginArray                     // begin array
    55  	scanArrayValue                     // just finished array value
    56  	scanEndArray                       // end array (implies scanArrayValue if possible)
    57  	scanSkipSpace                      // space byte; can skip; known to be last "continue" result
    58  	scanEnd                            // top-level value ended *before* this byte; known to be first "stop" result
    59  	scanError                          // hit an error, scanner.err.
    60  
    61  	// This limits the max nesting depth to prevent stack overflow.
    62  	// This is permitted by https://tools.ietf.org/html/rfc7159#section-9
    63  	maxNestingDepth = 10000
    64  )
    65  
    66  type (
    67  	scanner struct {
    68  		step       func(*scanner, byte) scanStatus
    69  		parseState []int
    70  		endTop     bool
    71  		err        error
    72  		index      int
    73  	}
    74  )
    75  
    76  // Scan returns the number of bytes scanned and if there was any error
    77  // in trying to reach the end of data.
    78  func Scan(data []byte) (int, error) {
    79  	s := &scanner{}
    80  	_ = checkValid(data, s)
    81  	return s.index, s.err
    82  }
    83  
    84  // checkValid verifies that data is valid JSON-encoded data.
    85  // scan is passed in for use by checkValid to avoid an allocation.
    86  func checkValid(data []byte, scan *scanner) error {
    87  	scan.reset()
    88  	for _, c := range data {
    89  		scan.index++
    90  		if scan.step(scan, c) == scanError {
    91  			return scan.err
    92  		}
    93  	}
    94  	if scan.eof() == scanError {
    95  		return scan.err
    96  	}
    97  	return nil
    98  }
    99  
   100  func isSpace(c byte) bool {
   101  	return c == ' ' || c == '\t' || c == '\r' || c == '\n'
   102  }
   103  
   104  func (s *scanner) reset() {
   105  	s.step = stateBeginValue
   106  	s.parseState = s.parseState[0:0]
   107  	s.err = nil
   108  }
   109  
   110  // eof tells the scanner that the end of input has been reached.
   111  // It returns a scan status just as s.step does.
   112  func (s *scanner) eof() scanStatus {
   113  	if s.err != nil {
   114  		return scanError
   115  	}
   116  	if s.endTop {
   117  		return scanEnd
   118  	}
   119  	s.step(s, ' ')
   120  	if s.endTop {
   121  		return scanEnd
   122  	}
   123  	if s.err == nil {
   124  		s.err = fmt.Errorf("unexpected end of JSON input")
   125  	}
   126  	return scanError
   127  }
   128  
   129  // pushParseState pushes a new parse state p onto the parse stack.
   130  // an error state is returned if maxNestingDepth was exceeded, otherwise successState is returned.
   131  func (s *scanner) pushParseState(c byte, newParseState int, successState scanStatus) scanStatus {
   132  	s.parseState = append(s.parseState, newParseState)
   133  	if len(s.parseState) <= maxNestingDepth {
   134  		return successState
   135  	}
   136  	return s.error(c, "exceeded max depth")
   137  }
   138  
   139  // popParseState pops a parse state (already obtained) off the stack
   140  // and updates s.step accordingly.
   141  func (s *scanner) popParseState() {
   142  	n := len(s.parseState) - 1
   143  	s.parseState = s.parseState[0:n]
   144  	if n == 0 {
   145  		s.step = stateEndTop
   146  		s.endTop = true
   147  	} else {
   148  		s.step = stateEndValue
   149  	}
   150  }
   151  
   152  // stateBeginValueOrEmpty is the state after reading `[`.
   153  func stateBeginValueOrEmpty(s *scanner, c byte) scanStatus {
   154  	if c <= ' ' && isSpace(c) {
   155  		return scanSkipSpace
   156  	}
   157  	if c == ']' {
   158  		return stateEndValue(s, c)
   159  	}
   160  	return stateBeginValue(s, c)
   161  }
   162  
   163  // stateBeginValue is the state at the beginning of the input.
   164  func stateBeginValue(s *scanner, c byte) scanStatus {
   165  	if c <= ' ' && isSpace(c) {
   166  		return scanSkipSpace
   167  	}
   168  	switch c {
   169  	case '{':
   170  		s.step = stateBeginStringOrEmpty
   171  		return s.pushParseState(c, parseObjectKey, scanBeginObject)
   172  	case '[':
   173  		s.step = stateBeginValueOrEmpty
   174  		return s.pushParseState(c, parseArrayValue, scanBeginArray)
   175  	case '"':
   176  		s.step = stateInString
   177  		return scanBeginLiteral
   178  	case '-':
   179  		s.step = stateNeg
   180  		return scanBeginLiteral
   181  	case '0': // beginning of 0.123
   182  		s.step = state0
   183  		return scanBeginLiteral
   184  	case 't': // beginning of true
   185  		s.step = stateT
   186  		return scanBeginLiteral
   187  	case 'f': // beginning of false
   188  		s.step = stateF
   189  		return scanBeginLiteral
   190  	case 'n': // beginning of null
   191  		s.step = stateN
   192  		return scanBeginLiteral
   193  	}
   194  	if '1' <= c && c <= '9' { // beginning of 1234.5
   195  		s.step = state1
   196  		return scanBeginLiteral
   197  	}
   198  	return s.error(c, "looking for beginning of value")
   199  }
   200  
   201  // stateBeginStringOrEmpty is the state after reading `{`.
   202  func stateBeginStringOrEmpty(s *scanner, c byte) scanStatus {
   203  	if c <= ' ' && isSpace(c) {
   204  		return scanSkipSpace
   205  	}
   206  	if c == '}' {
   207  		n := len(s.parseState)
   208  		s.parseState[n-1] = parseObjectValue
   209  		return stateEndValue(s, c)
   210  	}
   211  	return stateBeginString(s, c)
   212  }
   213  
   214  // stateBeginString is the state after reading `{"key": value,`.
   215  func stateBeginString(s *scanner, c byte) scanStatus {
   216  	if c <= ' ' && isSpace(c) {
   217  		return scanSkipSpace
   218  	}
   219  	if c == '"' {
   220  		s.step = stateInString
   221  		return scanBeginLiteral
   222  	}
   223  	return s.error(c, "looking for beginning of object key string")
   224  }
   225  
   226  // stateEndValue is the state after completing a value,
   227  // such as after reading `{}` or `true` or `["x"`.
   228  func stateEndValue(s *scanner, c byte) scanStatus {
   229  	n := len(s.parseState)
   230  	if n == 0 {
   231  		// Completed top-level before the current byte.
   232  		s.step = stateEndTop
   233  		s.endTop = true
   234  		return stateEndTop(s, c)
   235  	}
   236  	if c <= ' ' && isSpace(c) {
   237  		s.step = stateEndValue
   238  		return scanSkipSpace
   239  	}
   240  	ps := s.parseState[n-1]
   241  	switch ps {
   242  	case parseObjectKey:
   243  		if c == ':' {
   244  			s.parseState[n-1] = parseObjectValue
   245  			s.step = stateBeginValue
   246  			return scanObjectKey
   247  		}
   248  		return s.error(c, "after object key")
   249  	case parseObjectValue:
   250  		if c == ',' {
   251  			s.parseState[n-1] = parseObjectKey
   252  			s.step = stateBeginString
   253  			return scanObjectValue
   254  		}
   255  		if c == '}' {
   256  			s.popParseState()
   257  			return scanEndObject
   258  		}
   259  		return s.error(c, "after object key:value pair")
   260  	case parseArrayValue:
   261  		if c == ',' {
   262  			s.step = stateBeginValue
   263  			return scanArrayValue
   264  		}
   265  		if c == ']' {
   266  			s.popParseState()
   267  			return scanEndArray
   268  		}
   269  		return s.error(c, "after array element")
   270  	}
   271  	return s.error(c, "")
   272  }
   273  
   274  // stateEndTop is the state after finishing the top-level value,
   275  // such as after reading `{}` or `[1,2,3]`.
   276  // Only space characters should be seen now.
   277  func stateEndTop(s *scanner, c byte) scanStatus {
   278  	if c != ' ' && c != '\t' && c != '\r' && c != '\n' {
   279  		// Complain about non-space byte on next call.
   280  		s.error(c, "after top-level value")
   281  	}
   282  	return scanEnd
   283  }
   284  
   285  // stateInString is the state after reading `"`.
   286  func stateInString(s *scanner, c byte) scanStatus {
   287  	if c == '"' {
   288  		s.step = stateEndValue
   289  		return scanContinue
   290  	}
   291  	if c == '\\' {
   292  		s.step = stateInStringEsc
   293  		return scanContinue
   294  	}
   295  	if c < 0x20 {
   296  		return s.error(c, "in string literal")
   297  	}
   298  	return scanContinue
   299  }
   300  
   301  // stateInStringEsc is the state after reading `"\` during a quoted string.
   302  func stateInStringEsc(s *scanner, c byte) scanStatus {
   303  	switch c {
   304  	case 'b', 'f', 'n', 'r', 't', '\\', '/', '"':
   305  		s.step = stateInString
   306  		return scanContinue
   307  	case 'u':
   308  		s.step = stateInStringEscU
   309  		return scanContinue
   310  	}
   311  	return s.error(c, "in string escape code")
   312  }
   313  
   314  // stateInStringEscU is the state after reading `"\u` during a quoted string.
   315  func stateInStringEscU(s *scanner, c byte) scanStatus {
   316  	if '0' <= c && c <= '9' || 'a' <= c && c <= 'f' || 'A' <= c && c <= 'F' {
   317  		s.step = stateInStringEscU1
   318  		return scanContinue
   319  	}
   320  	// numbers
   321  	return s.error(c, "in \\u hexadecimal character escape")
   322  }
   323  
   324  // stateInStringEscU1 is the state after reading `"\u1` during a quoted string.
   325  func stateInStringEscU1(s *scanner, c byte) scanStatus {
   326  	if '0' <= c && c <= '9' || 'a' <= c && c <= 'f' || 'A' <= c && c <= 'F' {
   327  		s.step = stateInStringEscU12
   328  		return scanContinue
   329  	}
   330  	// numbers
   331  	return s.error(c, "in \\u hexadecimal character escape")
   332  }
   333  
   334  // stateInStringEscU12 is the state after reading `"\u12` during a quoted string.
   335  func stateInStringEscU12(s *scanner, c byte) scanStatus {
   336  	if '0' <= c && c <= '9' || 'a' <= c && c <= 'f' || 'A' <= c && c <= 'F' {
   337  		s.step = stateInStringEscU123
   338  		return scanContinue
   339  	}
   340  	// numbers
   341  	return s.error(c, "in \\u hexadecimal character escape")
   342  }
   343  
   344  // stateInStringEscU123 is the state after reading `"\u123` during a quoted string.
   345  func stateInStringEscU123(s *scanner, c byte) scanStatus {
   346  	if '0' <= c && c <= '9' || 'a' <= c && c <= 'f' || 'A' <= c && c <= 'F' {
   347  		s.step = stateInString
   348  		return scanContinue
   349  	}
   350  	// numbers
   351  	return s.error(c, "in \\u hexadecimal character escape")
   352  }
   353  
   354  // stateNeg is the state after reading `-` during a number.
   355  func stateNeg(s *scanner, c byte) scanStatus {
   356  	if c == '0' {
   357  		s.step = state0
   358  		return scanContinue
   359  	}
   360  	if '1' <= c && c <= '9' {
   361  		s.step = state1
   362  		return scanContinue
   363  	}
   364  	return s.error(c, "in numeric literal")
   365  }
   366  
   367  // state1 is the state after reading a non-zero integer during a number,
   368  // such as after reading `1` or `100` but not `0`.
   369  func state1(s *scanner, c byte) scanStatus {
   370  	if '0' <= c && c <= '9' {
   371  		s.step = state1
   372  		return scanContinue
   373  	}
   374  	return state0(s, c)
   375  }
   376  
   377  // state0 is the state after reading `0` during a number.
   378  func state0(s *scanner, c byte) scanStatus {
   379  	if c == '.' {
   380  		s.step = stateDot
   381  		return scanContinue
   382  	}
   383  	if c == 'e' || c == 'E' {
   384  		s.step = stateE
   385  		return scanContinue
   386  	}
   387  	return stateEndValue(s, c)
   388  }
   389  
   390  // stateDot is the state after reading the integer and decimal point in a number,
   391  // such as after reading `1.`.
   392  func stateDot(s *scanner, c byte) scanStatus {
   393  	if '0' <= c && c <= '9' {
   394  		s.step = stateDot0
   395  		return scanContinue
   396  	}
   397  	return s.error(c, "after decimal point in numeric literal")
   398  }
   399  
   400  // stateDot0 is the state after reading the integer, decimal point, and subsequent
   401  // digits of a number, such as after reading `3.14`.
   402  func stateDot0(s *scanner, c byte) scanStatus {
   403  	if '0' <= c && c <= '9' {
   404  		return scanContinue
   405  	}
   406  	if c == 'e' || c == 'E' {
   407  		s.step = stateE
   408  		return scanContinue
   409  	}
   410  	return stateEndValue(s, c)
   411  }
   412  
   413  // stateE is the state after reading the mantissa and e in a number,
   414  // such as after reading `314e` or `0.314e`.
   415  func stateE(s *scanner, c byte) scanStatus {
   416  	if c == '+' || c == '-' {
   417  		s.step = stateESign
   418  		return scanContinue
   419  	}
   420  	return stateESign(s, c)
   421  }
   422  
   423  // stateESign is the state after reading the mantissa, e, and sign in a number,
   424  // such as after reading `314e-` or `0.314e+`.
   425  func stateESign(s *scanner, c byte) scanStatus {
   426  	if '0' <= c && c <= '9' {
   427  		s.step = stateE0
   428  		return scanContinue
   429  	}
   430  	return s.error(c, "in exponent of numeric literal")
   431  }
   432  
   433  // stateE0 is the state after reading the mantissa, e, optional sign,
   434  // and at least one digit of the exponent in a number,
   435  // such as after reading `314e-2` or `0.314e+1` or `3.14e0`.
   436  func stateE0(s *scanner, c byte) scanStatus {
   437  	if '0' <= c && c <= '9' {
   438  		return scanContinue
   439  	}
   440  	return stateEndValue(s, c)
   441  }
   442  
   443  // stateT is the state after reading `t`.
   444  func stateT(s *scanner, c byte) scanStatus {
   445  	if c == 'r' {
   446  		s.step = stateTr
   447  		return scanContinue
   448  	}
   449  	return s.error(c, "in literal true (expecting 'r')")
   450  }
   451  
   452  // stateTr is the state after reading `tr`.
   453  func stateTr(s *scanner, c byte) scanStatus {
   454  	if c == 'u' {
   455  		s.step = stateTru
   456  		return scanContinue
   457  	}
   458  	return s.error(c, "in literal true (expecting 'u')")
   459  }
   460  
   461  // stateTru is the state after reading `tru`.
   462  func stateTru(s *scanner, c byte) scanStatus {
   463  	if c == 'e' {
   464  		s.step = stateEndValue
   465  		return scanContinue
   466  	}
   467  	return s.error(c, "in literal true (expecting 'e')")
   468  }
   469  
   470  // stateF is the state after reading `f`.
   471  func stateF(s *scanner, c byte) scanStatus {
   472  	if c == 'a' {
   473  		s.step = stateFa
   474  		return scanContinue
   475  	}
   476  	return s.error(c, "in literal false (expecting 'a')")
   477  }
   478  
   479  // stateFa is the state after reading `fa`.
   480  func stateFa(s *scanner, c byte) scanStatus {
   481  	if c == 'l' {
   482  		s.step = stateFal
   483  		return scanContinue
   484  	}
   485  	return s.error(c, "in literal false (expecting 'l')")
   486  }
   487  
   488  // stateFal is the state after reading `fal`.
   489  func stateFal(s *scanner, c byte) scanStatus {
   490  	if c == 's' {
   491  		s.step = stateFals
   492  		return scanContinue
   493  	}
   494  	return s.error(c, "in literal false (expecting 's')")
   495  }
   496  
   497  // stateFals is the state after reading `fals`.
   498  func stateFals(s *scanner, c byte) scanStatus {
   499  	if c == 'e' {
   500  		s.step = stateEndValue
   501  		return scanContinue
   502  	}
   503  	return s.error(c, "in literal false (expecting 'e')")
   504  }
   505  
   506  // stateN is the state after reading `n`.
   507  func stateN(s *scanner, c byte) scanStatus {
   508  	if c == 'u' {
   509  		s.step = stateNu
   510  		return scanContinue
   511  	}
   512  	return s.error(c, "in literal null (expecting 'u')")
   513  }
   514  
   515  // stateNu is the state after reading `nu`.
   516  func stateNu(s *scanner, c byte) scanStatus {
   517  	if c == 'l' {
   518  		s.step = stateNul
   519  		return scanContinue
   520  	}
   521  	return s.error(c, "in literal null (expecting 'l')")
   522  }
   523  
   524  // stateNul is the state after reading `nul`.
   525  func stateNul(s *scanner, c byte) scanStatus {
   526  	if c == 'l' {
   527  		s.step = stateEndValue
   528  		return scanContinue
   529  	}
   530  	return s.error(c, "in literal null (expecting 'l')")
   531  }
   532  
   533  // stateError is the state after reaching a syntax error,
   534  // such as after reading `[1}` or `5.1.2`.
   535  func stateError(s *scanner, c byte) scanStatus {
   536  	return scanError
   537  }
   538  
   539  // error records an error and switches to the error state.
   540  func (s *scanner) error(c byte, context string) scanStatus {
   541  	s.step = stateError
   542  	s.err = fmt.Errorf("invalid character <<%c>> %s", c, context)
   543  	return scanError
   544  }
   545
View as plain text